Power Set

作者 QIFAN 日期 2016-10-01
Power Set

Write a method to return all subsets of a set.
写一个能够返回所有子集的方法。

思路

关键词:set,所以没有duplicate key

假设S={a1, a2, a3, ... , an}

  • case n = 0:
    1 subarray: {}
  • case n = 1:
    2 subarray: {}, {a1}
  • case n = 2:
    4 subarray: {}, {a1}, {a2}, {a1a2}
  • case n = 3:
    8 subarray: {}, {a1}, {a2}, {a1a2}, {a3}, {a1a3}, {a2a3}, {a1a2a3} = case 2 + (case 2 + a3)

现在我们可以看出规律,case n = (case n-1) + (case(n-1) + an),也就是前n个数的子集包括前n-1的子集和这n-1的自己依次加上第n个元素构成的新集合。
要计算P(n),先计算P(n-1),再将an加到每一个克隆子集中

解题

  • 迭代
    如果是bottom up的方法。从0到size

    public List<List<Integer>> getSubsets(List<Integer> set) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    if (set == null) return result;
    result.add(new ArrayList<Integer>());
    if (set.size() == 0) return result;
    for(int i = 0; i < set.size(); i++) {
    //要提前存储好当前result的size
    int sz = result.size();
    for (int j = 0; j < sz; j++) {
    // 必须要重新建一个object,而不仅仅是reference
    ArrayList<Integer> temp = new ArrayList<>(result.get(j));
    temp.add(set.get(i));
    result.add(temp);
    }
    }
    return result;
    }
  • 递归
    top down的方法,本质和迭代是一样的
    Base Case: index == set.size,子集为空集

    public List<List<Integer>> getSubsets(List<Integer> set) {
    if (set == null) return result;
    return getSubsets(set, 0);
    }
    public List<List<Integer>> getSubsets(List<Integer> set, int index) {
    ArrayList<ArrayList<Integer>> subsets;
    if (index == set.size()) {
    subsets = new ArrayList<>();
    subsets.add(new ArrayList<Integer>());
    } else {
    subsets = getSubsets(set, index + 1);
    int item = set.get(index);
    ArrayList<ArrayList<Integer>> newSubsets = ArrayList<>();
    for (ArrayList<Integer> subset: subsets) {
    ArrayList<Integer> extraSubset = new ArrayList(subset);
    extraSubset.add(item);
    newSubsets.add(extraSubset);
    }
    subsets.add(newSubsets);
    }
    return subsets;
    }
  • 位运算
    size为n的set共有2^n个子集,是不是觉得可以用传说中的位运算?

    public ArrayList<ArrayList<Integer>> getSubsets(List<Integer> set) {
    ArrayList<ArrayList<Integer>> subsets = new ArrayList<>();
    int max = 1 << set.size(); // 计算子集个数2^n
    for (int k = 0; k < max; k++) {
    ArrayList<Integer> subset = convertIntToSet(k, set);
    subsets.add(subset);
    }
    return subsets;
    }
    public ArrayList<Integer> convertIntToSet(int x, ArrayList<Integer> set) {
    ArrayList<Integer> subset = new ArrayList<>();
    int index = 0;
    for(int k = x; k > 0; k >>= 1) {
    if ((k & 1) == 1) { // 等同于 i % 2 == 1,不过还是没懂
    subset.add(set.get(index++));
    }
    }
    return subset;
    }

分析

各种方法的时间复杂度都是O(n * 2^n),但是位运算会快很多很多