LeetCode num078

Problem

Subsets
Given a set of distinct integers, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Solution

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
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S)
{
vector<vector<int> > result = subsetsWithoutSort (S);
for (int i = 0; i < result.size(); i++)
{
sort(result[i].begin(), result[i].end());
}
return result;
}
vector<vector<int> > subsetsWithoutSort(vector<int> &S)
{
int i, j, k;
vector<int> love, leave, empty;
vector<vector<int> > family, result;
if (S.size() == 1)
{
love.push_back(S[0]);
result.push_back(love);
result.push_back(empty);
return result;
}
for (j = 1; j < S.size(); j++)
{
leave.push_back(S[j]);
}
family = subsets(leave);
for (k = 0; k < family.size(); k++)
{
result.push_back(family[k]);
family[k].push_back(S[0]);
result.push_back(family[k]);
}
return result;
}
};

Comment

  1. 全排列;
  2. 动态规划;
  3. 类似背包。

LeetCode num077

Problem

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

1
2
3
4
5
6
7
8
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Solution

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
class Solution {
public:
vector<vector<int> > combine(int n, int k)
{
vector<int> input;
vector<vector<int> > result;
if (n == 0 || k == 0 || n < k)
{
return result;
}
for (int i = 1; i <= n; i++)
{
input.push_back(i);
}
result = love(input, k);
for (int i = 0; i < result.size(); i++)
{
sort(result[i].begin(), result[i].end());
}
return result;
}
vector<vector<int> > love (vector<int> input, int k)
{
vector<vector<int> > result, leave, all;
vector<int> process;
int i, dispute = input[0];
if (k == 1)
{
for (i = 0; i < input.size(); i++)
{
process.push_back(input[i]);
result.push_back(process);
process.clear();
}
return result;
}
else if (input.size() == k)
{
result.push_back(input);
return result;
}
input.erase(input.begin());
leave = love(input, k - 1);
for (i = 0; i < leave.size(); i++)
{
leave[i].push_back(dispute);
result.push_back(leave[i]);
}
all = love(input, k);
for (i = 0; i < all.size(); i++)
{
result.push_back(all[i]);
}
return result;
}
};

Comment

  1. 递归。