【道德经·第三十五章】执大象，天下往。往而不害，安平太。乐与饵，过客止，道之出口，淡乎其无味，视之不足见，听之不足闻，用之不足既。
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列。
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
| vector<vector<int> > permute(vector<int>& nums) {
vector<vector<int> > res;
vector<int> out;
int n = nums.size();
bool *visted = new bool[n];
fill(visted, visted+n, false);
dfs(nums, res, out, visted);
return res;
}
void dfs(vector<int>& nums, vector<vector<int> >& res, vector<int>& out, bool* visted) {
if(out.size() == nums.size()) {
res.push_back(out);
return;
}
for(int i = 0; i < nums.size(); i++) {
if(visted[i] == true) continue;
out.push_back(nums[i]);
visted[i] = true;
dfs(nums, res, out, visted);
visted[i] = false;
out.pop_back();
}
}
|
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
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
| void dfs(vector<int>& nums, bool* visted, vector<int>& cur, vector<vector<int> >& res) {
if(cur.size() >= nums.size()) {
res.push_back(cur);
return;
}
for(int i = 0; i < nums.size(); ++i) {
if(visted[i] || (i>0 && nums[i]==nums[i-1] && visted[i-1]==false)) continue;
vis[i] = 1;
cur.push_back(nums[i]);
dfs(nums, visted, cur, res);
cur.pop_back();
vis[i] = 0;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> > res;
vector<int> cur;
if(nums.empty()) return res;
sort(nums.begin(), nums.end());
int n = nums.size();
bool *visted = new bool[n];
fill(visted, visted+n, false);
dfs(nums, visted, cur, res);
return res;
}
|
给你一个整数数组 nums ，找出 nums 的下一个排列。
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
| void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i;
for(i = n-1; i > 0; i--) {
if(nums[i] > nums[i-1]) {
break;
}
}
if(i == 0) {
reverse(nums.begin(), nums.end());
return;
}
int j;
for(j = n-1; j >= i; j--) {
if(nums[j] > nums[i-1]) {
swap(nums[j], nums[i-1]);
break;
}
}
sort(nums.begin()+i, nums.end());
}
|
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列。
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
| vector<string> Permutation(string str) {
int n = str.size();
vector<string> res;
string cur;
bool *visited = new bool[n];
fill(visited, visited+n, false);
sort(str.begin(), str.end());
dfs(str, res, cur, visited);
return res;
}
void dfs(string& str, vector<string>& res, string& cur, bool* visited) {
if(cur.size() == str.size()) {
res.push_back(cur);
return;
}
for(int i = 0; i < str.size(); i++) {
if(visited[i] == true) continue;
if(i>0 && str[i]==str[i-1] && visited[i-1]==false) continue;
visited[i] = true;
cur.push_back(str[i]);
dfs(str, res, cur, visited);
cur.pop_back();
visited[i] = false;
}
}
|
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> out;
dfs(n, k, res, out, 1);
return res;
}
void dfs(int n, int k, vector<vector<int>>& res, vector<int>& out, int start) {
if(out.size() == k) {
res.push_back(out);
return;
}
for(int i = start; i <= n; i++) {
out.push_back(i);
dfs(n, k, res, out, i+1);
out.pop_back();
}
}
|
找出nums（无重复）中可以使数字和为目标数target的所有不同组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| vector<vector<int>> combinationSum(vector<int>& nums, int target) {
vector<vector<int>> res;
vector<int> out;
dfs(nums, target, res, out, 0);
return res;
}
void dfs(vector<int>& nums, int target, vector<vector<int>>& res, vector<int>& out, int start) {
if(target < 0)
return;
if(target == 0) {
res.push_back(out);
return;
}
for(int i = start; i < nums.size(); i++) {
out.push_back(nums[i]);
dfs(nums, target-nums[i], res, out, i);
out.pop_back();
}
}
|
组合总和带重复元素。
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
| vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
vector<vector<int> > res;
vector<int> out;
sort(candidates.begin(), candidates.end());
dfs(candidates, target, res, out, 0);
return res;
}
void dfs(vector<int>& candidates, int target, vector<vector<int> >& res, vector<int>& out, int start) {
if(target < 0) return;
if(target == 0) {
res.push_back(out);
return;
}
for(int i = start; i < candidates.size(); i++) {
if(i>start && candidates[i]==candidates[i-1]) continue;
out.push_back(candidates[i]);
dfs(candidates, target-candidates[i], res, out, i+1);
out.pop_back();
}
}
|
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：1、只使用数字1到9每个数字；2、最多使用一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int> > res;
vector<int> out;
dfs(k, n, res, out, 1);
return res;
}
void dfs(int k, int n, vector<vector<int> >& res, vector<int>& out, int start) {
if(n < 0) return;
if(n==0 && out.size()==k) {
res.push_back(out);
return;
}
for(int i = start; i <= 9; i++) {
out.push_back(i);
dfs(k, n-i, res, out, i+1);
out.pop_back();
}
}
|
从不同整数组成的数组nums中找出并返回总和为 target 的元素组合的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num<=i && dp[i-num]<INT_MAX-dp[i])
dp[i] += dp[i-num];
}
}
return dp[target];
}
|
位我上者，灿烂星空；道德律令，在我心中。