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
answerlist and an emptycurrentcombination to store all valid combinations.Define a recursive function with the current
index,remainingTarget, andcurrentcombination.Add
currenttoanswerwhenremainingTargetbecomes0, as the selected values now form a valid combination.Pick the current candidate when it does not exceed
remainingTarget, recurse with the sameindexto 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
answercontaining all valid combinations.
Dry Run
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.
Be the first to add a comment.