LeetCode-40. Combination Sum II

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]]

题解：dfs，没有想到去重的好办法，set暴力去重了。。

class Solution {public: static void dfs(int n, vector t, vector &v, set> &ans, int target, int k) { for (int i = k; i < n; i++) { if (t[i] < target) { v.push_back(t[i]); dfs(n, t, v, ans, target - t[i], i + 1); v.pop_back(); } if (t[i] == target) { v.push_back(t[i]); ans.insert(v); v.pop_back(); return; } } } vector> combinationSum2(vector& candidates, int target) { int n = candidates.size(); sort(candidates.begin(), candidates.end()); set> sans; vector v; if (n == 0) { return vector>(); } dfs(n, candidates, v, sans, target, 0); vector> ans(sans.begin(), sans.end()); return ans; }};

参考了一下讨论区，最后面增加一步去重，感觉对递归的理解还是不够。

class Solution {public: static void dfs(int n, vector t, vector &v, vector> &ans, int target, int k) { for (int i = k; i < n; i++) { if (t[i] < target) { v.push_back(t[i]); dfs(n, t, v, ans, target - t[i], i + 1); v.pop_back(); } if (t[i] == target) { v.push_back(t[i]); ans.push_back(v); v.pop_back(); return; } while (t[i] == t[i + 1]) { i++; } } } vector> combinationSum2(vector& candidates, int target) { int n = candidates.size(); sort(candidates.begin(), candidates.end()); vector v; if (n == 0) { return vector>(); } vector> ans; dfs(n, candidates, v, ans, target, 0); return ans; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。