2014
11-18

# LeetCode-Subsets[暴力枚举]

### 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:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

// LeetCode, Subsets
// 增量构造法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());  // 输出要求有序
vector<vector<int> > result;
vector<int> path;
subsets(S, path, 0, result);
return result;
}

private:
static void subsets(const vector<int> &S, vector<int> &path, int step,
vector<vector<int> > &result) {
if (step == S.size()) {
result.push_back(path);
return;
}
// 不选S[step]
subsets(S, path, step + 1, result);
// 选S[step]
path.push_back(S[step]);
subsets(S, path, step + 1, result);
path.pop_back();
}
};

位向量法

// LeetCode, Subsets
// 位向量法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());  // 输出要求有序

vector<vector<int> > result;
vector<bool> selected(S.size(), false);
subsets(S, selected, 0, result);
return result;
}

private:
static void subsets(const vector<int> &S, vector<bool> &selected, int step,
vector<vector<int> > &result) {
if (step == S.size()) {
vector<int> subset;
for (int i = 0; i < S.size(); i++) {
if (selected[i]) subset.push_back(S[i]);
}
result.push_back(subset);
return;
}
// 不选S[step]
selected[step] = false;
subsets(S, selected, step + 1, result);
// 选S[step]
selected[step] = true;
subsets(S, selected, step + 1, result);
}
};

迭代

// LeetCode, Subsets
// 迭代版，时间复杂度O(2^n)，空间复杂度O(1)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end()); // 输出要求有序
vector<vector<int> > result(1);
for (auto elem : S) {
result.reserve(result.size() * 2);
auto half = result.begin() + result.size();
copy(result.begin(), half, back_inserter(result));
for_each(half, result.end(), [&elem](decltype(result[0]) &e){
e.push_back(elem);
});
}
return result;
}
};

二进制法

// LeetCode, Subsets
// 二进制法，时间复杂度O(2^n)，空间复杂度O(1)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end()); // 输出要求有序
vector<vector<int> > result;
const size_t n = S.size();
vector<int> v;

for (size_t i = 0; i < 1 << n; i++) {
for (size_t j = 0; j < n; j++) {
if (i & 1 << j) v.push_back(S[j]);
}
result.push_back(v);
v.clear();
}
return result;
}
};

Java代码:

public class Solution {
public static List<List<Integer>> subsets(int[] S) {
int all = 1 << S.length;
Arrays.sort(S);
List<List<Integer>> subsetsList = new ArrayList();
for (int i = 0; i < all; i++) {
int b = 1;
List<Integer> tmpList = new ArrayList();
for (int j = 0; j < S.length; j++) {
if ((i & b) != 0) {
}
b <<= 1;
}
}
return subsetsList;
}
}

Subsets II

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false