Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.Example 1:
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ]Example 2:
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]题目：返回所有和为target的集合。其中原始元素集合中无重复的元素，可以重复使用原集合中的元素。返回的结果不能有相同的集合，如[2,3,2]和[2,2,3]。
思路：回溯法，参考A general approach to backtracking questions。因为可以使用重复的元素，因此再进行递归时从第i个元素开始。
工程代码下载
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res; vector<int> vec; backtracking(res, vec, candidates, 0, target); return res; } private: void backtracking(vector<vector<int>>& res, vector<int>& vec, const vector<int>& candidate, int start, int remain){ if(remain == 0){ res.push_back(vec); return; } if(remain < 0) return; for(int i = start; i < candidate.size(); ++i){ vec.push_back(candidate[i]); // not i + 1 because we can reuse same elements backtracking(res, vec, candidate, i, remain-candidate[i]); vec.pop_back(); } } };Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]题目: 给定一个候选元素的数组candidates，找出满足和为target的所有子集。candidates可能包含重复的元素，只能使用candidates中存在的元素。
思路: 和4sum类似，只是这里的递归深度不定，递归返回的条件是remain已经等于0，参考A general approach to backtracking questions。同时由于题目的特殊性，candidates中的元素和target均为正数，所以当remain小于0时也可以直接返回，减少递归的次数。为了防止结果中出现重复的集合，先对candidates排序，同时在每层递归中跳过已经判断过的相同元素。
工程代码下载
#include<iostream> #include<vector> #include<algorithm> using namespace std; class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<vector<int> > res; vector<int> vec; helper(candidates, res, vec, 0, target); return res; } private: void helper(vector<int>& candidates, vector<vector<int>>& res, vector<int>& vec, int start, int remain){ /** All numbers (including target) will be positive integers. **/ if(remain < 0) return; if(remain == 0){ res.push_back(vec); return; } for(int i = start; i< candidates.size(); ++i){ /** skip duplicates */ if(i > start && candidates[i] == candidate[i-1]) continue; vec.push_back(candidates[i]); helper(candidates, res, vec, i+1, remain-candidates[i]); vec.pop_back(); } } }; int main(int argc, char const *argv[]) { Solution sln; vector<int> testcase{10,1,2,7,6,1,5}; vector<vector<int>> res = sln.combinationSum2(testcase, 8); for(auto vec: res){ for(auto i : vec) cout << i << ","; cout << endl; } return 0; }Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Note:
All numbers will be positive integers.The solution set must not contain duplicate combinations.Example 1:
Input: k = 3, n = 7 Output: [[1,2,4]]Example 2:
Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]题目：从集合{1,2,3,4,5,6,7,8,9}中选择k个数使其满足和为n，返回所有可能的组合。
思路：回溯。类似4Sum。递归深度为k，当已经选择了k个元素之后，判断其和是否为n，如果是则将该组合保存下来并回溯，否则直接回溯返回。
工程代码下载
class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; vector<int> vec; if(k <= 0) return res; helper(res, vec, k, n, 1); return res; } private: void helper(vector<vector<int>>& res, vector<int>& vec, int k, int remain, int start){ if(k < 0 && remain < 0) return; if(k == 0){ if(remain == 0) res.push_back(vec); return; } for(int i = start; i <= 9; ++i){ vec.push_back(i); helper(res, vec, k-1, remain-i, i+1); vec.pop_back(); } } };Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7.Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
题目：返回和为target的组合的个数。其中nums中无重复的元素，不同的元素排列看作是不同的组合结果。
思路：采用前缀和的思想，参考DP Solution 。先判断和为1的组合个数，那么和为2的组合个数可以等于comb[2] = comb[1], if nums[j] =1，直到和为target。可以先对nums进行排序。
工程代码下载
class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<unsigned int> comb(target + 1); comb[0] = 1; for(int i = 1; i <= target; ++i){ for(int j = 0; j < nums.size(); ++j){ if(i - nums[j] >= 0) comb[i] += comb[i-nums[j]]; } } return comb[target]; } };