Combination Sum - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find all unique combinations of candidates that sum to a target, where each candidate can be used unlimited times.
Initialize an empty list res to store all valid combinations and an empty list sol to build the current combination.
Get the length n of the candidates array and store candidates as nums.
Define a backtrack function that takes index i and current sum cur_sum.
In backtrack, if cur_sum equals target, append a copy of sol to res and return.
If cur_sum exceeds target or i equals n, return to stop exploring this path.
Make two choices: skip the current candidate by calling backtrack(i+1, cur_sum).
Include the current candidate by appending nums[i] to sol, calling backtrack(i, cur_sum + nums[i]), and then popping nums[i] from sol to backtrack.
Start the backtracking process by calling backtrack(0, 0).
Return res as the list of all valid combinations.

Code Solution

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res, sol = [], []
        nums = candidates
        n = len(nums)
        
        def backtrack(i, cur_sum):
            if cur_sum == target:
                res.append(sol[:])
                return
            
            if cur_sum > target or i == n:
                return

            backtrack(i+1, cur_sum)

            sol.append(nums[i])
            backtrack(i, cur_sum+nums[i])
            sol.pop()
        
        backtrack(0, 0)
        return res
        # Time: O(n**t)
        # Space: O(n)

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> sol;
        backtrack(candidates, target, 0, 0, sol, res);
        return res;
    }

private:
    void backtrack(vector<int>& candidates, int target, int start, int curSum, vector<int>& sol, vector<vector<int>>& res) {
        if (curSum == target) {
            res.push_back(sol);
            return;
        }
        if (curSum > target || start == candidates.size()) {
            return;
        }

        // Skip the current candidate
        backtrack(candidates, target, start + 1, curSum, sol, res);

        // Include the current candidate
        sol.push_back(candidates[start]);
        backtrack(candidates, target, start, curSum + candidates[start], sol, res);
        sol.pop_back();
    }
};

import java.util.*;

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> sol = new ArrayList<>();
        backtrack(candidates, target, 0, 0, sol, res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, int curSum, List<Integer> sol, List<List<Integer>> res) {
        if (curSum == target) {
            res.add(new ArrayList<>(sol));
            return;
        }
        if (curSum > target || start == candidates.length) {
            return;
        }

        // Skip the current candidate
        backtrack(candidates, target, start + 1, curSum, sol, res);

        // Include the current candidate
        sol.add(candidates[start]);
        backtrack(candidates, target, start, curSum + candidates[start], sol, res);
        sol.remove(sol.size() - 1);
    }
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const res = [];
    const sol = [];
    backtrack(candidates, target, 0, 0, sol, res);
    return res;
};

function backtrack(candidates, target, start, curSum, sol, res) {
    if (curSum === target) {
        res.push([...sol]);
        return;
    }
    if (curSum > target || start === candidates.length) {
        return;
    }

    // Skip the current candidate
    backtrack(candidates, target, start + 1, curSum, sol, res);

    // Include the current candidate
    sol.push(candidates[start]);
    backtrack(candidates, target, start, curSum + candidates[start], sol, res);
    sol.pop();
}

Detailed Explanation

Understanding the Problem

The "Combination Sum" problem asks us to find all unique combinations of numbers from a given list of positive integers called candidates that add up to a specific target value. A key twist is that each number in candidates may be used an unlimited number of times in each combination.

For instance, given candidates = [2, 3, 6, 7] and target = 7, a valid result would be [[2, 2, 3], [7]]. Here, [2, 2, 3] sums to 7 and uses the number 2 more than once.

Recursive Backtracking Approach

This problem is ideally suited for a backtracking algorithm. We start at the first index of the candidates array and decide at each step whether to include the current number or skip it. If we include it, we stay at the current index to allow repeated use. If we skip it, we move to the next index.

The backtracking function takes the current index and a running sum of the selected numbers. If the running sum equals the target, we store a copy of the current combination. If it exceeds the target or we've processed all candidates, we stop exploring that path.

This recursive approach ensures all valid paths are explored, and backtracking removes the last element to try new possibilities at each level.

Why This Works

The use of backtracking is powerful here because we avoid unnecessary computations. For example, once our current sum exceeds the target, there's no need to go further down that path. Additionally, by only moving forward in the candidate list or staying on the current index (to allow reuse), we prevent generating duplicate combinations in different orders (like [2,3,2] vs [2,2,3]).

Time and Space Complexity

The time complexity is difficult to quantify precisely due to the branching factor and pruning, but in the worst case, it is exponential, roughly O(2^T) where T is the target value. Each recursive call explores paths that build up to the target.

The space complexity is O(T) for the recursion stack and the space used to store intermediate combinations.

Conclusion

The "Combination Sum" problem is a classic application of recursive backtracking with a twist — unlimited reuse of elements. It strengthens understanding of recursion, state tracking, and optimization through pruning. Practicing this problem builds a strong foundation for tackling more complex variations involving permutations, subsets, and partitioning problems.

Get Personalized Support at AlgoMap Bootcamp 💡