-
Notifications
You must be signed in to change notification settings - Fork 0
/
Combination Sum.cpp
175 lines (153 loc) · 6.1 KB
/
Combination Sum.cpp
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
///@file Combination Sum
/*
Given a set of candidate numbers (C) 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.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
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]
*/
///@author zhaowei
///@date 2015.06.18
///@version 1.0
///@date 2015.09.04
///@version 1.1
///@date 2015.09.24
///@version 1.2
///@date 2016.04.09
///@version 1.3
///@date October 11, 2018
///@version 1.4
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution_v1
{
public:
///@brief 计算和为目标值的所有可能组合
///@param candidates 候选数字数组
///@param target 目标值
///@return 返回所有可能的数字组合,其中数字按照升序排序,没有重复的数组
///@note 用回溯的思路解题。先将候选数组排序,然后按照从低到高的顺序逐一尝试,将目标值减去小于目标值的候选数字,直到目标值为0得到一个可能的组合。
// 否则就返回上一个元素,选择下一个可能的数字。直到找到所有可能的组合。时间复杂度为O(n^2),空间复杂度为O(1)
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
sort(candidates.begin(), candidates.end()); // 排序
vector<int> combination;
calCombination(candidates, 0, target, combination); // 递归求解
return combinations;
}
///@brief 计算可能的和为目标值的组合
///@param candidates 候选数字数组
///@param index 在候选数字数组中的下标
///@param target 目标值
///@param combination 可能的一个组合
void calCombination(vector<int>& candidates, int index, int target, vector<int>& combination)
{
if (target == 0) // 如果目标值减为0就算找到了一个组合
{
combinations.push_back(combination); // 压入当前候选数字
return;
}
for (int i = index; i < candidates.size() && target >= candidates[i]; i++)
{
combination.push_back(candidates[i]); // 压入当前候选数字
calCombination(candidates, i, target-candidates[i], combination); // 递归调用自身求解
combination.pop_back(); // 不满足的情况要回溯,需要弹出当前的数字,并尝试下一个候选数组中的数字
}
}
private:
vector<vector<int>> combinations; // 所有可能的组合集合
};
class Solution_v1_1 {
public:
///@brief 给定一组数组(乱序)和一个给定值,计算所有可能的组合和为给定值,其中元素能够重复出现。
///@param candidates 乱序数组
///@param target 目标值
///@return 返回所有的可能组合
///@note 递归回溯法。首先对数组进行排序,然后逐个尝试每个组合。尝试的元素必须小于等于目标值,如果目标值被减为零,则可以将一个结果压入最终的结果集合。否则就弹出上一次压入的元素,
// 并进行下一个元素的尝试。
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> rslt;
if (candidates.empty()) return rslt;
sort(candidates.begin(), candidates.end());
vector<int> comb;
dfs(rslt, comb, candidates, 0, target);
return rslt;
}
///@brief 递归回溯法求组合
///@param rslt 组合集合
///@param comb 一个组合
///@param cadidates 候选数组
///@param indx 遍历到了候选数组中的元素下标
///@param target 目标值
///@return 无
void dfs(vector<vector<int>>& rslt, vector<int>& comb, vector<int>& candidates, int indx, int target) {
if (!target) rslt.push_back(comb);
else {
for (int i = indx; i < candidates.size() && candidates[i] <= target; i++) {
comb.push_back(candidates[i]);
dfs(rslt, comb, candidates, i, target - candidates[i]);
comb.pop_back();
}
}
}
};
class Solution {
public:
///@brief 给定一个数组,不含有重复元素,找到所有和为目标值的元素组合,其中元素可以重复出现。
///@param candidates 待选元素数组
///@param target 目标值
///@return 返回和为目标值的所有可能组合。
///@note 1. 通过调用一个深度优先遍历的递归函数来实现。
// 2. 在进入递归函数前,需要先将待选数组按照升序排个序,这样便于递归结束。
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> rslt;
if (candidates.empty()) return rslt;
vector<int> comb;
sort(candidates.begin(), candidates.end());
dfs(rslt, candidates, comb, 0, target);
return rslt;
}
///@brief 深度优先遍历递归函数
///@param rslt 结果数组
///@param candidates 候选元素数组
///@param comb 一个有效的组合
///@param index 遍历候选数组的当前元素下标
///@param target 目标值
///@return 无
///@note 1. 递归时并未将index自增,这是因为题意允许相同元素多次重复出现。
// 2. 递归的结束通过target是否小于等于当前数组元素来完成。
void dfs(vector<vector<int>>& rslt, vector<int>& candidates, vector<int>& comb, int index, int target) {
if (!target) {
rslt.push_back(comb);
return;
}
for(int i = index; i < candidates.size() && candidates[i] <= target; i++) {
comb.push_back(candidates[i]);
dfs(rslt, candidates, comb, i, target - candidates[i]);
comb.pop_back();
}
return;
}
};
int main()
{
vector<int> test;
test.push_back(3);
test.push_back(2);
test.push_back(4);
test.push_back(7);
test.push_back(6);
Solution slt;
vector<vector<int>> rslt = slt.combinationSum(test, 12);
Solution_v1_1 s11;
vector<vector<int>> r11 = s11.combinationSum(test, 12);
return 0;
}