Combination Sum Algorithm
The Combination Sum algorithm is a popular backtracking algorithm used to solve the classic problem of finding all the unique combinations in a collection of candidate numbers that add up to a given target. This problem is often encountered in various programming contests, interviews, and real-world applications, such as optimizing financial portfolios, resource allocation, or picking items from a menu with a budget constraint. The input usually consists of an array of integers (the candidate numbers), a target sum, and the constraint that each candidate number can be used multiple times in a combination. The output is a list of lists, where each inner list represents a unique combination of numbers that add up to the target sum.
To solve this problem, the algorithm starts by taking an empty list as the current combination and the entire input array as the remaining candidates. It then iteratively selects a candidate from the remaining candidates and adds it to the current combination. If the sum of the current combination equals the target sum, the combination is added to the output list. If the sum is less than the target, the algorithm continues to explore further combinations using the current candidate and the remaining candidates. However, if the sum exceeds the target, the algorithm backtracks by removing the last added candidate and continues exploring other candidates. The algorithm repeats this process until all combinations are found. This approach ensures that the search space is traversed efficiently and all valid combinations are discovered without redundant explorations.
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
combination_set.clear();
sort(candidates.begin(), candidates.end());
vector<int> nums;
DFS(nums, target, candidates, 0);
return move(combination_set);
}
void DFS(vector<int>& nums, int target, vector<int>& candidates, int position) {
if (target < 0) return;
if (target == 0) {
combination_set.push_back(nums);
return;
}
if (position >= candidates.size())
return;
DFS(nums, target, candidates, position + 1);
int value = candidates[position];
for (int i = 1; i * value <= target; i++) {
for (int j = 0; j < i; j++)
nums.push_back(value);
DFS(nums, target - i * value, candidates, position + 1);
for (int j = 0; j < i; j++)
nums.pop_back();
}
}
private:
vector<vector<int>> combination_set;
};
