Problem Statement

Given an array of positive integers candidates (with no duplicates) and a target integer target, find all unique combinations of candidates where the chosen numbers sum up to target. A number from candidates can be chosen multiple times in the combination.

• Input:
  • candidates: an array of unique positive integers.
  • target: a positive integer representing the target sum.
• Output:
  • A list of all unique combinations of numbers from candidates that sum up to target.

LeetCode

• https://leetcode.com/problems/combination-sum/

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Examples

Example 1:

Input: nums = [2, 3, 5, 4], target = 7
Output:
[
  [2, 2, 3],
  [3, 4],
  [5, 2]
]

Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
5 and 2 are candidates, and 5 + 2 = 7.
3 and 4 are candidates, and 3 + 4 = 7.
There are total three combinations.

Example 2:

Input: nums = [2], target = 1
Output: []

Explanation:
There is no possible way to get the target 1 when the element in the array is bigger than target.

Example 3:

Input: nums = [1], target  = 1
Output:[
        [1]
       ]

Different Approaches

1️⃣ Backtracking

Dry Run:

Initial Setup

1. Input:
   • candidates = [2, 3, 5]
   • target = 8
   • currentCombination = [] (Initially, the current combination is empty)
   • start = 0 (Initially, start from the first element of the candidates array)
2. First Call: We call backtrack(candidates, 8, [], result, 0).

Step-by-Step Dry Run

Iteration 1 (starting from index 0)

1. Start iterating with i = 0 (element 2):
   • Current combination:[2]
   • Remaining target:8 - 2 = 6
2. Call backtrack(candidates, 6, [2], result, 0) (recur with same index since repetition is allowed).

Iteration 2 (starting from index 0)

3. Again start iterating with i = 0 (element 2):
   • Current combination:[2, 2]
   • Remaining target:6 - 2 = 4
4. Call backtrack(candidates, 4, [2, 2], result, 0).

Iteration 3 (starting from index 0)

5. Start iterating with i = 0 (element 2):
   • Current combination:[2, 2, 2]
   • Remaining target:4 - 2 = 2
6. Call backtrack(candidates, 2, [2, 2, 2], result, 0).

Iteration 4 (starting from index 0)

7. Start iterating with i = 0 (element 2):
   • Current combination:[2, 2, 2, 2]
   • Remaining target:2 - 2 = 0 (target reached)
8. Valid combination:[2, 2, 2, 2] (add to result).
9. Backtrack: Remove the last element (2), so the combination becomes [2, 2, 2].

Iteration 5 (continue from index 1)

10. Now try i = 1 (element 3):
    • Current combination:[2, 2, 2, 3]
    • Remaining target:2 - 3 = -1 (overshoot)
11. Backtrack: Remove 3. Combination becomes [2, 2, 2].

Iteration 6 (continue from index 2)

12. Now try i = 2 (element 5):
    • Current combination:[2, 2, 2, 5]
    • Remaining target:2 - 5 = -3 (overshoot)
13. Backtrack: Remove 5. Combination becomes [2, 2, 2].
14. Backtrack: Remove 2. Combination becomes [2, 2].

Iteration 7 (continue from index 1)

15. Now try i = 1 (element 3):
    • Current combination:[2, 2, 3]
    • Remaining target:4 - 3 = 1.
16. Call backtrack(candidates, 1, [2, 2, 3], result, 1).

Iteration 8 (continue from index 1)

17. Try i = 1 (element 3):
    • Current combination:[2, 2, 3, 3]
    • Remaining target:1 - 3 = -2 (overshoot)
18. Backtrack: Remove 3. Combination becomes [2, 2, 3].

Iteration 9 (continue from index 2)

19. Now try i = 2 (element 5):
    • Current combination:[2, 2, 5]
    • Remaining target:3 - 5 = -2 (overshoot)
20. Backtrack: Remove 5. Combination becomes [2, 2].
21. Backtrack: Remove 2. Combination becomes [2].

Iteration 10 (continue from index 1)

22. Now try i = 1 (element 3):
    • Current combination:[2, 3]
    • Remaining target:6 - 3 = 3.
23. Call backtrack(candidates, 3, [2, 3], result, 1).

Iteration 11 (continue from index 1)

24. Try i = 1 (element 3):
    • Current combination:[2, 3, 3]
    • Remaining target:3 - 3 = 0 (target reached)
25. Valid combination:[2, 3, 3] (add to result).
26. Backtrack: Remove 3. Combination becomes [2, 3].

Iteration 12 (continue from index 2)

27. Now try i = 2 (element 5):
    • Current combination:[2, 5]
    • Remaining target:3 - 5 = -2 (overshoot)
28. Backtrack: Remove 5. Combination becomes [2].
29. Backtrack: Remove 2. Combination becomes [].

Iteration 13 (continue from index 1)

30. Now try i = 1 (element 3):
    • Current combination:[3]
    • Remaining target:8 - 3 = 5.
31. Call backtrack(candidates, 5, [3], result, 1).

Iteration 14 (continue from index 1)

32. Try i = 1 (element 3):
    • Current combination:[3, 3]
    • Remaining target:5 - 3 = 2.
33. Call backtrack(candidates, 2, [3, 3], result, 1).

Iteration 15 (continue from index 1)

34. Try i = 1 (element 3):
    • Current combination:[3, 3, 3]
    • Remaining target:2 - 3 = -1 (overshoot)
35. Backtrack: Remove 3. Combination becomes [3, 3].

Iteration 16 (continue from index 2)

36. Now try i = 2 (element 5):
    • Current combination:[3, 5]
    • Remaining target:5 - 5 = 0 (target reached)
37. Valid combination:[3, 5] (add to result).
38. Backtrack: Remove 5. Combination becomes [3].
39. Backtrack: Remove 3. Combination becomes [].

Iteration 17 (continue from index 2)

40. Try i = 2 (element 5):
    • Current combination:[5]
    • Remaining target:8 - 5 = 3.
41. Call backtrack(candidates, 3, [5], result, 2).

Iteration 18 (continue from index 2)

42. Try i = 2 (element 5):
    • Current combination:[5, 5]
    • Remaining target:3 - 5 = -2 (overshoot)
43. Backtrack: Remove 5. Combination becomes [5].
44. Backtrack: Remove 5. Combination becomes [].

Final Result:

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Code With For Loop:

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void backtrack(vector<int>& candidates, int target, vector<int>& currentCombination, vector<vector<int>>& allCombinations, int start) {
        // Base case: If the target becomes zero, we found a valid combination
        if (target == 0) {
            allCombinations.push_back(currentCombination);
            return;
        }

        // Iterate over the candidates, starting from `start`
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) {
                // If the candidate is greater than the remaining target, skip it
                continue;
                // or we can break it, since in sorted array every element next to it will be greater obviously.
            }

            // Choose the current candidate, Include the candidate
            currentCombination.push_back(candidates[i]);

            // Recur: We can reuse the same candidate, so we pass `i` as the next index
            backtrack(candidates, target - candidates[i], currentCombination, allCombinations, i);

            // Backtrack: Remove the last candidate and try the next one
            currentCombination.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> currentCombination;

        backtrack(candidates, target, currentCombination, result, 0);

        return result;
    }
};

int main() {
    Solution solution;
    vector<int> candidates = {2, 3, 5};
    int target = 8;

    vector<vector<int>> result = solution.combinationSum(candidates, target);

    // Output the result
    cout << "Combinations that sum to " << target << ":\n";
    for (const auto& combination : result) {
        cout << "[ ";
        for (int num : combination) {
            cout << num << " ";
        }
        cout << "]\n";
    }

    return 0;
}

Explanation:

1. combinationSum Function:
   • This is the main function that initiates the backtracking. It takes candidates and target as input, and returns all possible combinations that sum up to the target.
2. backtrack Function:
   • Base case: If target == 0, it means we've found a valid combination, and we add it to the result.
   • Loop: We iterate over the candidates starting from index start. We only consider candidates that are less than or equal to the current target (since we don't want to overshoot the target).
   • Recursive call: We recursively call the backtrack function with the reduced target (target - candidates[i]).
   • Backtracking: After returning from recursion, we remove the last added element and try the next candidate.

Complexity Analysis:

• Time Complexity: O(2 ^ n), where n is the number of elements in the candidates array.

Dry Run Without For Loop:

Code Without For Loop:

#include <vector>
using namespace std;

class Solution {
public:
    void solve(vector<vector<int>>& result, vector<int>& candidates, int target, int index, vector<int>& output) {
        // Base case: if target is met exactly, add current combination to result
        if (target == 0) {
            result.push_back(output);
            return;
        }
        
        // Base case:
        // If we reach the end of the list or target becomes negative, stop recursion
        if (index == candidates.size() || target < 0) {
            return;
        }

        // Option 1: Include the current candidate
        output.push_back(candidates[index]);
        solve(result, candidates, target - candidates[index], index, output); // Use same index to allow reuse of the same element

        // Backtrack by removing the last added element
        output.pop_back();

        // Option 2:
        // Exclude the current candidate and move to the next
        solve(result, candidates, target, index + 1, output);
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> output;
        
        solve(result, candidates, target, 0, output);
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(2 ^ n), where n is the number of elements in candidates.