首页 > ACM题库 > LeetCode > LeetCode-Subsets[暴力枚举]
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],
  []
]

标签: Array Backtracking Bit Manipulation
分析

每个元素,都有两种选择,选或者不选。

增量构造法

// 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();
    }
};

 位向量法

开一个位向量bool selected[n],每个元素可以选或者不选。

// 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;
    }
};

 二进制法

本方法的前提是:集合的元素不超过int 位数。用一个int 整数表示位向量,第i 位为1,则表示
选择S[i],为0 则不选择。例如S={A,B,C,D},则0110=6 表示子集{B,C}。这种方法最巧妙。因为它不仅能生成子集,还能方便的表示集合的并、交、差等集合运算。设两个集合的位向量分别为B1 和B2,则$B_1\cup B_2, B_1 \cap B_2, B_1 \triangle B_2$分别对应集合的并、交、对称差。
二进制法,也可以看做是位向量法,只不过更加优化。

// 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) {
					tmpList.add(S[j]);
				}
				b <<= 1;
			}
			subsetsList.add(tmpList);
		}
		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