39. Combination Sum

Description

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Intuition

The problem can be visualized as a tree where each node represents a choice of whether to include a candidate number in the current combination. By exploring all possible paths in this tree, we can find all unique combinations that sum up to the target.

Approach

1. Backtracking with Recursion: - Define a recursive helper function to explore all possible combinations. - Use a list temp to store the current combination and a list ans to store all valid combinations. - Start from the first candidate and explore two paths: including the candidate and not including the candidate. - If the current sum equals the target, add the current combination to the answer list. - If the current sum exceeds the target or the index exceeds the length of candidates, backtrack by removing the last added candidate and exploring the next candidate.
2. Recursive Function: - Base Case: If the sum of the current combination equals the target, add the combination to the answer list. - If the sum exceeds the target or if there are no more candidates to consider, return to explore other paths. - Recursive Case: Include the current candidate and call the function with the updated sum. Exclude the current candidate and call the function with the next candidate.
3. Start the Recursion: - Start the recursion from the first index and an initial sum of 0.

Complexity

Time Complexity:

O(2^n), where n is the length of the candidates array. This is because, in the worst case, we might have to explore all possible combinations.

Space Complexity:

O(target/min(candidates)), where min(candidates) is the smallest number in the candidates array. This accounts for the maximum depth of the recursion tree and the space needed to store the current combination.

Code

C++

class Solution {
public:
    vector> combinationSum(vector& candidates, int target) {
        vector> output;
        set> uniqueCombinations;
        
        function, int)> recursion = [&](vector currArr, int currTarget) {
            if (currTarget == 0) {
                vector sortedCurrArr = currArr;
                sort(sortedCurrArr.begin(), sortedCurrArr.end());
                if (uniqueCombinations.find(sortedCurrArr) == uniqueCombinations.end()) {
                    uniqueCombinations.insert(sortedCurrArr);
                    output.push_back(sortedCurrArr);
                }
                return;
            }
            for (int num : candidates) {
                if (currTarget - num >= 0) {
                    currArr.push_back(num);
                    recursion(currArr, currTarget - num);
                    currArr.pop_back(); // backtrack
                }
            }
        };
        
        recursion({}, target);
        return output;
    }
};

Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        self.find(candidates, 0, ans, temp, 0, target)
        for combination in ans:
            print(combination)
        return ans

    def find(self, nums: List[int], index: int, ans: List[List[int]], temp: List[int], sum: int, target: int):
        if sum == target:
            ans.append(temp.copy())
            return
        if sum > target or index == len(nums):
            return
        temp.append(nums[index])
        self.find(nums, index, ans, temp, sum + nums[index], target)
        temp.pop()
        self.find(nums, index + 1, ans, temp, sum, target)

Java

class Solution {
    public List> combinationSum(int[] candidates, int target) {
        List> ans = new ArrayList<>();
        List temp = new ArrayList<>();
        find(candidates, 0, ans, temp, 0, target);
        for (List no : ans) {
            System.out.println(no);
        }
        return ans;
    }

    public void find(int[] nums, int index, List> ans, List temp, int sum, int target) {
        if (sum == target) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        if (sum > target || index == nums.length) {
            return;
        }
        temp.add(nums[index]);
        find(nums, index, ans, temp, sum + nums[index], target);
        temp.remove(temp.size() - 1);
        find(nums, index + 1, ans, temp, sum, target);
    }
}

JavaScript

const combinationSum = function(candidates, target) {
    const ans = [];
    const temp = [];
    const find = (nums, index, ans, temp, sum, target) => {
        if (sum === target) {
            ans.push([...temp]);
            return;
        }
        if (sum > target || index === nums.length) {
            return;
        }
        temp.push(nums[index]);
        find(nums, index, ans, temp, sum + nums[index], target);
        temp.pop();
        find(nums, index + 1, ans, temp, sum, target);
    };
    find(candidates, 0, ans, temp, 0, target);
    return ans;
};