Combination Sum

How it works

This optimized backtracking solution avoids exploring useless paths by using sorting + early stopping.

• We sort the numbers so that once a number makes the sum exceed the target, all numbers after it will also exceed the target - we can safely stop exploring further (break / return).
• At each position, we try every number starting from index i, allowing reuse of the same number.
• We build combinations step-by-step, and whenever the running total equals the target, we record the current list.

Sorting + pruning significantly reduces unnecessary recursion.

Steps

1. Sort nums so we can stop early when the sum exceeds the target.
2. Define a recursive function dfs(i, currentList, total):
   • If total == target:
     • Add a copy of currentList to the result.
     • Return.
3. Loop j from i to end of list:
   • If total + nums[j] > target, stop the loop (no need to check larger numbers).
   • Add nums[j] to currentList.
   • Call dfs(j, currentList, total + nums[j]) (reuse allowed).
   • Remove last element to backtrack.
4. Start recursion with dfs(0, [], 0) and return the result.

This ensures we explore only valid combinations while eliminating unnecessary work.

Complexity

• Time complexity: O(2 ^ frac{t}{m})
• Space complexity: O(frac{t}{m})

Where t is the given target and m is the minimum value in nums.

Things to watch for

Moving to Next Index After Including an Element

Since each number can be used unlimited times, after including nums[i], you should stay at index i, not move to i + 1. Moving forward prevents reusing the same element.

Generating Duplicate Combinations

Without maintaining an index, you might generate [2,3] and [3,2] as separate combinations. Always iterate from the current index forward, never backward, to ensure each combination is generated only once in sorted order.

Not Pruning When Sum Exceeds Target

Continuing recursion when total > target wastes time exploring invalid paths. With sorted input, you can break early once total + nums[j] > target since all subsequent numbers are larger.

from typing import List

class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        nums.sort()

        def dfs(i, cur, total):
            if total == target:
                res.append(cur.copy())
                return

            for j in range(i, len(nums)):
                if total + nums[j] > target:
                    return
                cur.append(nums[j])
                dfs(j, cur, total + nums[j])
                cur.pop()

        dfs(0, [], 0)
        return res

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        dfs(0, {}, 0, nums, target);
        return res;
    }

    void dfs(int i, vector<int> cur, int total, vector<int>& nums, int target) {
        if (total == target) {
            res.push_back(cur);
            return;
        }

        for (int j = i; j < nums.size(); j++) {
            if (total + nums[j] > target) {
                return;
            }
            cur.push_back(nums[j]);
            dfs(j, cur, total + nums[j], nums, target);
            cur.pop_back();
        }
    }
};