# 39. 组合总和
力扣原题链接（点我直达） (opens new window)
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
1
2
3
4
5
6
2
3
4
5
6
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
1
2
3
4
5
6
7
2
3
4
5
6
7
# 1、经典回溯模板
执行用时：8 ms, 在所有 C++ 提交中击败了83.99%的用户
内存消耗：7.7 MB, 在所有 C++ 提交中击败了100.00%的用户
void combinationSumCore(vector<vector<int>>& res, vector<int>& candidates, int target, vector<int>& tmp, int sum, int begin) {
if (sum == target) {
res.push_back(tmp);
}
else {
for (int i = begin; i < candidates.size(); ++i) {
if (sum + candidates[i] <= target) {
tmp.push_back(candidates[i]);
combinationumCore(res, candidates, target, tmp, sum + candidates[i], i);
tmp.pop_back();
}else{
return;
}
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> tmp;
sort(candidates.begin(), candidates.end());
combinationSumCore(res, candidates, target, tmp, 0, 0);//sum 与 index
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 40. 组合总和 II
力扣原题链接（点我直达） (opens new window)
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
1
2
3
4
5
6
2
3
4
5
6
# 1、关键在于去重
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.1 MB, 在所有 C++ 提交中击败了100.00%的用户
void combinationSum2Core(vector<int>& candidates, vector<vector<int>>& result, vector<int>& temp, int target, int begin, int sum) {
if (sum == target)
{
result.push_back(temp);
return;
}
for (int i = begin; i < candidates.size(); ++i)
{
if (i > begin && candidates[i] == candidates[i - 1]) continue;
if (sum + candidates[i] <= target) {
temp.push_back(candidates[i]);
combinationSum2Core(candidates, result, temp, target, i + 1, sum + candidates[i]);
temp.pop_back();
}
else
return;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int>temp;
vector<vector<int>> result;
combinationSum2Core(candidates, result, temp, target, 0, 0);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 46. 全排列
力扣原题链接（点我直达） (opens new window)
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 1、使用全排列函数next_permutation函数
执行用时：4 ms, 在所有 C++ 提交中击败了88.65%的用户
内存消耗：6.9 MB, 在所有 C++ 提交中击败了100.00%的用户
vector<vector<int>> permute(vector<int>& nums) {
if (nums.size() == 0) return vector<vector<int>>();
vector<vector<int>> result;
sort(nums.begin(), nums.end());
do {
result.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return result;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 2、DFS + 回溯
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.4 MB, 在所有 C++ 提交中击败了100.00%的用户
void permuteCore(vector<vector<int>> &result, vector<int>&nums,int begin) {
if (begin == nums.size() - 1) {
result.push_back(nums);
return;
}
for (int i = begin; i < nums.size(); ++i) {
std::swap(nums[i], nums[begin]);
permuteCore(result, nums, begin+1);
std::swap(nums[i], nums[begin]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
if (nums.size() == 0) return vector<vector<int>>();
vector<vector<int>> result;
permuteCore(result, nums, 0);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 47. 全排列 II
力扣原题链接（点我直达） (opens new window)
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
1
2
3
4
5
6
7
2
3
4
5
6
7
# 1、回溯 + 剪枝
执行用时：20 ms, 在所有 C++ 提交中击败了37.15%的用户
内存消耗：9 MB, 在所有 C++ 提交中击败了100.00%的用户
https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-jian-zhi-deng-jie-ji-chu-quan-pai-lie-by-ge/
/*
针对同一层次的计算，对连续的相同的元素只选取一个进行后续的替换，即可等价于基础全排列。例如，
当前层次是[1,2, 1, 2], 我们可以只选取第一次出现的元素作为替换： 对于第一个元素1， 第一次出现，则其结果为1与[2, 1, 2]的所有全排列的连接，标记1已使用；
对于第二个元素2，2未使用，则其结果为2与[1, 1, 2]的全排列的连接，并标记2已使用; 对于第3个元素1，其已使用，跳过；对于最后一个元素2，由于2已使用，跳过。
*/
void permuteUniqueCore(vector<int>& nums, vector<vector<int>>& result, int index)
{
if (index == nums.size())result.push_back(nums);
else {
unordered_map<int, int> mp;
for (int i = index; i < nums.size(); ++i)//index的起始点表示选择列表的范围
{
/*剪枝：同层次此元素已使用多次，在使用必然会照成重复全排列，所以直接跳过*/
if (mp.count(nums[i]) > 0)continue;
/*决策路径加上这个决策*/
swap(nums[index], nums[i]);
/*进入下一步决策*/
permuteUniqueCore(nums, result, index + 1);
/*决策路径移除这个决策*/
swap(nums[index], nums[i]);
/*标记此层次这个元素已使用一次了*/
mp[nums[i]]++;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums)
{
//vector<int> track(nums.begin(), nums.end());
sort(nums.begin(), nums.end());
vector<vector<int>> result;
permuteUniqueCore(nums, result, 0);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 面试题 08.08. 有重复字符串的排列组合 (opens new window)
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
示例1:
输入：S = "qqe"
输出：["eqq","qeq","qqe"]
1
2
2
示例2:
输入：S = "ab"
输出：["ab", "ba"]
1
2
2
提示:
- 字符都是英文字母。
- 字符串长度在[1, 9]之间。
# 0、直接用next_permutation函数来做就可以，但是要记得先排序，而且是必须排序才可以
执行用时：4 ms, 在所有 C++ 提交中击败了94.10%的用户 内存消耗：7.2 MB, 在所有 C++ 提交中击败了66.42%的用户
vector<string> permutation(string S) {
vector<string> result;
sort(S.begin(), S.end());
do {
result.push_back(S);
} while (next_permutation(S.begin(), S.end()));
return result;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 1、回溯
执行用时：16 ms, 在所有 C++ 提交中击败了38.23%的用户
内存消耗：8.3 MB, 在所有 C++ 提交中击败了14.18%的用户
void permutationCore(vector<string>& result, int index, string &S) {
if (index == S.size()) {
result.push_back(S);
return;
}
unordered_map<char, int> unmp;
for (int i = index; i < S.size(); ++i) {
if (unmp[S[i]] >0)
continue;
std::swap(S[index], S[i]);
permutationCore(result, index + 1, S);
std::swap(S[i], S[index]);
unmp[S[i]]++;
}
}
vector<string> permutation(string S) {
vector<string> result;
sort(S.begin(), S.end());
permutationCore(result, 0, S);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 78. 子集
力扣原题链接（点我直达） (opens new window)
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 1、全部返回
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.9 MB, 在所有 C++ 提交中击败了100.00%的用户
void subsetsCore(vector<int>& nums, vector<vector<int>>& result, vector<int>&temp,int index)
{
result.push_back(temp); //因为是全部子集，所以要全部返回
for (int i = index; i < nums.size(); ++i)//index的起始点表示选择列表的范围
{
temp.push_back(nums[i]);
subsetsCore(nums, result, temp, i + 1);//这里是 i 而不是 index， 因为一到尾巴就算完事了
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
//sort(nums.begin(), nums.end());
vector<vector<int>> result;
vector<int> temp;
subsetsCore(nums, result,temp, 0);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 90. 子集 II
力扣原题链接（点我直达） (opens new window)
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 1、必须要排序才行，使用哈希表做去重处理
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.5 MB, 在所有 C++ 提交中击败了100.00%的用户
void subsetsWithDupCore(vector<int>& nums, vector<vector<int>>& result, vector<int>&temp,int index)
{
result.push_back(temp); //因为是全部子集，所以要全部返回
unordered_map<int, int> mp;
for (int i = index; i < nums.size(); ++i)//index的起始点表示选择列表的范围
{
if (mp[nums[i]] > 0) continue;
temp.push_back(nums[i]);
subsetsWithDupCore(nums, result, temp, i + 1);//这里是 i 而不是 index 因为一到尾巴就算完事了
temp.pop_back();
mp[nums[i]]++;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());//必不可少
vector<vector<int>> result;
vector<int> temp;
subsetsWithDupCore(nums, result,temp, 0);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 2、不用map保存结果，中间做去重处理
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.1 MB, 在所有 C++ 提交中击败了100.00%的用户
void subsetsWithDupCore(vector<int>& nums, vector<vector<int>>& result, vector<int>& temp, int index)
{
result.push_back(temp); //因为是全部子集，所以要全部返回
for (int i = index; i < nums.size(); ++i)//index的起始点表示选择列表的范围
{
if (i>index && nums[i]==nums[i-1]) continue;
temp.push_back(nums[i]);
subsetsWithDupCore(nums, result, temp, i + 1);//这里是 i 而不是 index 因为一到尾巴就算完事了
temp.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());//必不可少
vector<vector<int>> result;
vector<int> temp;
subsetsWithDupCore(nums, result, temp, 0);
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 679. 24 点游戏
力扣原题链接（点我直达） (opens new window)
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
示例 1:
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
1
2
3
2
3
示例 2:
输入: [1, 2, 1, 2]
输出: False
1
2
2
注意:
- 除法运算符
/表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。 - 每个运算符对两个数进行运算。特别是我们不能用
-作为一元运算符。例如，[1, 1, 1, 1]作为输入时，表达式-1 - 1 - 1 - 1是不允许的。 - 你不能将数字连接在一起。例如，输入为
[1, 2, 1, 2]时，不能写成 12 + 12 。
# 1、直接穷举
class Solution {
public boolean judgePoint24(int[] nums) {
double a = nums[0];
double b = nums[1];
double c = nums[2];
double d = nums[3];
return judge(a, b, c, d);
}
public boolean judge(double a, double b, double c, double d){
return
// a b
judge(a + b, c, d) ||
judge(a * b, c, d) ||
judge(a - b, c, d) ||
judge(b - a, c, d) ||
judge(a / b, c, d) ||
judge(b / a, c, d) ||
// b c
judge(c + b, a, d) ||
judge(c * b, a, d) ||
judge(c - b, a, d) ||
judge(b - c, a, d) ||
judge(c / b, a, d) ||
judge(b / c, a, d) ||
// c d
judge(c + d, a, b) ||
judge(c * d, a, b) ||
judge(c - d, a, b) ||
judge(d - c, a, b) ||
judge(c / d, a, b) ||
judge(d / c, a, b) ||
// b d
judge(b + d, a, c) ||
judge(b * d, a, c) ||
judge(b - d, a, c) ||
judge(d - b, a, c) ||
judge(b / d, a, c) ||
judge(d / b, a, c) ||
// a c
judge(a + c, b, d) ||
judge(a * c, b, d) ||
judge(a - c, b, d) ||
judge(c - a, b, d) ||
judge(a / c, b, d) ||
judge(c / a, b, d) ||
// a d
judge(a + d, b, c) ||
judge(a * d, b, c) ||
judge(a - d, b, c) ||
judge(d - a, b, c) ||
judge(a / d, b, c) ||
judge(d / a, b, c) ;
//
}
public boolean judge(double a, double b, double c){// 24 , 3 , 8
return
judge(a + b, c) ||
judge(a * b, c) ||
judge(a - b, c) ||
judge(b - a, c) ||
judge(a / b, c) ||
judge(b / a, c) ||
//
judge(c + b, a) ||
judge(c * b, a) ||
judge(c - b, a) ||
judge(b - c, a) ||
judge(c / b, a) ||
judge(b / c, a) ||
//
judge(c + a, b) ||
judge(c * a, b) ||
judge(c - a, b) ||
judge(a - c, b) ||
judge(c / a, b) ||
judge(a / c, b);
}
public boolean judge(double a, double b){
return
Math.abs(a + b - 24) < 0.001 ||
Math.abs(a - b - 24) < 0.001 ||
Math.abs(b - a - 24) < 0.001 ||
Math.abs(a * b - 24) < 0.001 ||
Math.abs(a / b - 24) < 0.001 ||
Math.abs(b / a - 24) < 0.001;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88