Combination Sum
题目描述:
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[[7],[2, 2, 3] ]
题目大意:
给定一个数组candidates和一个数字target，挑选candidates中元素，使这些元素的和等于target。其中的元素可以用多次。
dfs遍历所有的情况，注意控制边界即可。
题目代码:
class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(0, 0, candidates, target);return ans;}
private:vector<vector<int>>ans;vector<int>elements;void dfs(int cur, int sum, vector<int>&candidates, int target){if(sum > target)return ;if(sum == target){ans.push_back(elements);return ;}for(int i = cur; i < candidates.size(); i++){elements.push_back(candidates[i]);dfs(i, sum+candidates[i], candidates, target);elements.pop_back();}}
};