Combination Sum

18
0

Problem Statement

Given an array candidates containing distinct positive integers and an integer target, return all unique combinations with chosen numbers summing to target.

The same number can be chosen unlimited times. Two combinations are considered unique if the frequency of at least one chosen number differs.

Example 1

Input: candidates = [2, 3, 6, 7], target = 7

Output: [[2, 2, 3], [7]]

Explanation: The combination [2, 2, 3] sums to 7 and candidate 2 is reused. The candidate 7 alone also forms the target.

Example 2

Input: candidates = [2, 3, 5], target = 8

Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Explanation: Each listed combination sums to 8, and candidates can be reused any number of times.

Approach

The problem naturally forms a decision tree. At each index, two choices exist: pick the current candidate or skip the current candidate. Picking keeps the same index because the same candidate can be reused, while skipping moves to the next index.

The recursion carries the remaining target and the current combination. Reaching remaining target 0 means a valid combination has been formed. Positive candidates allow pruning whenever the current candidate exceeds the remaining target.

Algorithm

  • Initialize an empty answer list and an empty current combination to store all valid combinations.

  • Define a recursive function with the current index, remainingTarget, and current combination.

  • Add current to answer when remainingTarget becomes 0, as the selected values now form a valid combination.

  • Pick the current candidate when it does not exceed remainingTarget, recurse with the same index to allow reuse, and remove it after recursion returns to restore the previous state.

  • Skip the current candidate by recursively moving to index + 1, allowing other candidates to be explored without using the current one.

  • Continue until all candidates and target possibilities are processed, then return answer containing all valid combinations.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
void backtrack(int index, int target, vector<int>& candidates,
vector<int>& current, vector<vector<int>>& answer) {
// If target becomes 0, the current combination is valid.
if (target == 0) {
answer.push_back(current);
return;
}
// If all candidates are checked, no further combination is possible.
if (index == candidates.size()) {
return;
}
// If the current candidate can fit into the remaining target, pick it.
if (candidates[index] <= target) {
current.push_back(candidates[index]);
// Stay at the same index because the same candidate can be reused.
backtrack(index, target - candidates[index], candidates, current, answer);
// Remove the last picked element before trying another possibility.
current.pop_back();
} else {
// If the candidate is greater than target, it cannot be picked.
}
// Skip the current candidate and move to the next index.
backtrack(index + 1, target, candidates, current, answer);
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> answer;
vector<int> current;
// Start exploring combinations from index 0.
backtrack(0, target, candidates, current, answer);
return answer;
}
};
int main() {
vector<int> candidates = {2, 3, 6, 7};
int target = 7;
Solution solution;
vector<vector<int>> answer = solution.combinationSum(candidates, target);
for (auto combination : answer) {
cout << "[";
for (int index = 0; index < combination.size(); index++) {
// Add comma before every element except the first one.
if (index > 0) {
cout << ", ";
}
cout << combination[index];
}
cout << "] ";
}
return 0;
}

Complexity Analysis

Time Complexity: Let N be the number of candidates, T be the target, M be the smallest candidate, D = floor(T / M), X be the number of returned combinations, and K be the maximum length of one returned combination; a safe loose bound is O(2^(N + D) + X × K) because skip choices can advance across N candidates, pick choices can add up to D values, and copying answers costs O(X × K).

Space Complexity: O(N + D + X × K), where the recursion and current path can use O(N + D) auxiliary space and the returned combinations use O(X × K) output storage.

Interview follow-up Questions

Yes. Each candidate can be picked unlimited times.

RecursionTCS NQT

Read Similar Blogs

Comments0