Combination Sum

Practice here

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Brute Force - Recursion#

At each index i we make two choices: include candidates[i] (and stay at the same index since repetition is allowed, subtracting from target) or skip it (move to i+1 with target unchanged). The recursion backtracks after each choice by popping the element. When i reaches the end of the array, a valid combination is recorded only if target == 0. The key insight enabling reuse of the same element is passing i (not i+1) in the "pick" branch.

class Solution {
public:
    void combinationSumUtil(vector<int>& nums,vector<int>& temp, vector<vector<int>> &res, int target, int i)
    {
        if(i==nums.size())
        {
            if(target==0)
                res.push_back(temp);
            return;
        }

        if(nums[i] <= target){
            temp.push_back(nums[i]);
            combinationSumUtil(nums, temp, res, target-nums[i], i);
            temp.pop_back();
        }
        combinationSumUtil(nums, temp, res, target, i+1);
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> uniqueCombinations;
        vector<int> temp;
        combinationSumUtil(candidates, temp, uniqueCombinations, target, 0);
        return uniqueCombinations;
    }
};

Time Complexity: O(2^T), T -> target

Space Complexity: O(T)

When to Use Tabulation#

• If the problem is about counting the number of ways rather than listing them.
• If the interviewer specifically asks for iterative DP.