LeetCode: Combination Sum

第一次没考虑到要加个系数cur，因为必须从小到大排序，导致答案里有[1, 2]和[2, 1]，加入cur后就acm了

 1 class Solution {
 2 public:
 3     void dfs(vector<int> candidates, int target, int sum, vector<int> &save, vector<vector<int>> &ret, int cur) {
 4         if (sum > target) return;
 5         if (sum == target) {
 6             ret.push_back(save);
 7             return;
 8         }
 9         for (int i = cur; i < candidates.size(); i++) {
10             save.push_back(candidates[i]);
11             dfs(candidates, target, sum+candidates[i], save, ret, i);
12             save.pop_back();
13         }
14     }
15     vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
16         // Start typing your C/C++ solution below
17         // DO NOT write int main() function
18         sort(candidates.begin(), candidates.end());
19         int sum = 0;
20         vector<vector<int>> ret;
21         vector<int> save;
22         if (candidates.size() == 0) return ret;
23         int cur = 0;
24         dfs(candidates, target, sum, save, ret, cur);
25         return ret;
26     }
27 };

C#: C#有深浅拷贝的问题，这里浅拷贝的话最后的ans就一直是空。。。所以这里需要深拷贝出来。。。C++没有这个问题方便很多

 1 public class Solution {
 2     public List<List<int>> CombinationSum(int[] candidates, int target) {
 3         Array.Sort(candidates);
 4         int sum = 0;
 5         List<List<int>> ans = new List<List<int>>();
 6         List<int> tmp = new List<int>();
 7         if (candidates.Length == 0) return ans;
 8         int dep = 0;
 9         dfs(candidates, target, sum, ref tmp, ref ans, dep);
10         return ans;
11     }
12     void dfs(int[] candidates, int target, int sum, ref List<int> tmp, ref List<List<int>> ans, int dep)
13     {
14         if (sum > target) return;
15         if (sum == target) {
16             List<int> newTmp = new List<int>();
17             for (int i = 0; i < tmp.Count; i++) newTmp.Add(tmp[i]);
18             ans.Add(newTmp);
19             return;
20         }
21         for (int i = dep; i < candidates.Length; i++) {
22             tmp.Add(candidates[i]);
23             dfs(candidates, target, sum + candidates[i], ref tmp, ref ans, i);
24             tmp.RemoveAt(tmp.Count - 1);
25         }
26     }
27 }

View Code