Leetcode 39

#Leetcode 39| 来源: 网络整理| 查看: 265

Combination Sum I 题意

给一个set C，然后还有一个你要凑出来的数target，要求C里面的数可以使用任意多次，求方案（输出具体方案）。

思路

先将数组从大到小排序（cut），然后开始搜索。注意dfs模型：

void dfs(int pos, vector tmp, int sum) { if (Boundary) { //ok, time to judge return; } //not choose this num dfs(pos + 1, tmp, sum); //choose this num tmp.push_back(a[pos]); dfs(pos, tmp, sum + a[pos]); // it may be choose again, so position is still this position. tmp.pop_back(); } 代码 int tot, n, aim; vector res; class Solution { public: void dfs(int pos, vector tmp, vector&a, int sum) { if (sum >= aim || pos == a.size()) { if (sum == aim) { tot++; res.push_back(tmp); } return; } dfs(pos + 1, tmp, a, sum); tmp.push_back(a[pos]); dfs(pos, tmp, a, sum + a[pos]); tmp.pop_back(); } vector combinationSum(vector& a, int target) { tot = 0; res.clear(); aim = target; //init sort(a.begin(), a.end(), greater()); vector tt; dfs(0, tt, a, 0); return res; } }; Combination Sum II 题意

给定一个数组，数组内可能有重复元素，然后再给一个target，要求用数组内的数凑出target（结果不能有重复）

思路

基本和上面那道题一样，但是存在一个陷阱就是数组内的元素有重复元素但是结果不能有重复元素，比如我们数组为[4, 1, 1]，要凑出来5，结果应该是[4, 1]而不是[[4, 1], [4, 1]]。因此我们要对这种情况进行处理。

开始的时候用的一个很暴力的方法，直接用set套vector乱搞了一下。这样也对，但是时间复杂度会多一个log。比较好的方法是：当我们有2个1时，前面的1用了当前的1才能用。所以只需要加上这样一个判断就好了。

代码 //algorithm 1 int tot, n, aim; vector res; set tof; class Solution { public: void dfs(int pos, vector tmp, vector&a, int sum) { if (sum >= aim || pos == a.size()) { if (sum == aim) { tot++; if (tof.find(tmp) != tof.end()) return; tof.insert(tmp); res.push_back(tmp); } return; } dfs(pos + 1, tmp, a, sum); tmp.push_back(a[pos]); dfs(pos + 1, tmp, a, sum + a[pos]); tmp.pop_back(); } vector combinationSum2(vector& a, int target) { tot = 0; res.clear(); aim = target; tof.clear();//init sort(a.begin(), a.end(), greater()); vector tt; dfs(0, tt, a, 0); return res; } }; //algorithm 2 int tot, n, aim; vector res; int use[100005]; class Solution { public: void dfs(int pos, vector tmp, vector&a, int sum) { if (sum >= aim || pos == a.size()) { if (sum == aim) { tot++; res.push_back(tmp); } return; } dfs(pos + 1, tmp, a, sum); if (pos > 0 && a[pos] == a[pos - 1]) { if (use[pos - 1]) { use[pos] = 1; tmp.push_back(a[pos]); dfs(pos + 1, tmp, a, sum + a[pos]); tmp.pop_back(); use[pos] = 0; } } else { use[pos] = 1; tmp.push_back(a[pos]); dfs(pos + 1, tmp, a, sum + a[pos]); tmp.pop_back(); use[pos] = 0; } } vector combinationSum2(vector& a, int target) { tot = 0; res.clear(); aim = target;//init memset(use, 0, sizeof(use)); //init sort(a.begin(), a.end(), greater()); vector tt; dfs(0, tt, a, 0); return res; } }; Combination Sum III 题意

给出一个k和n，要求用k个数（每个数属于1~9）来组成n。每个数只能用一次，并且结果不能重复。

思路

还是裸dfs，只是需要记录一下用了几个数

代码 vector res; int target, kk; class Solution { public: int a[10]; void init(int n, int k) { res.clear(); target = n; kk = k; for (int i = 0; i = target || cnt >= kk) { if (sum == target && cnt == kk) res.push_back(tmp); return; } dfs(pos - 1, cnt, tmp, sum); tmp.push_back(a[pos]); dfs(pos - 1, cnt + 1, tmp, sum + a[pos]); tmp.pop_back(); } vector combinationSum3(int k, int n) { init(n, k); vector tmp; dfs(min(n, 9), 0, tmp, 0); return res; } };

【本文地址】

公司简介

联系我们