All Subsets

出处

Given a collection of integers that might contain duplicates, return all possible subsets.

Solution

如果不存在重复,那么对于当前节点,分为选取当前元素和不选取当前元素两条路径;

当存在重复时,那么对于当前节点,也可以分为选取当前元素和不选取当前元素。但是,如果没有选择当前元素,那么也一定不能选择后驱节点中与当前元素重复的任何元素,否则会产生完全重复的路径;

至于如果选取了当前元素,那么之后这个支线内部的重复问题,支线自然会解决,不需要关心。原因在于,子问题和原问题相互独立,子问题不需要关心如何来到当前节点。这样既保证了对于set{1,2,2},subset{1, 2}只被选择一次,也保证了{1,2,2}会被选择在内。

Complexity

时间复杂度 O(2n ),空间复杂度 O(n2 )

Code

ArrayList<ArrayList<Integer>> getSubset(int[] arr){
    ArrayLIst<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();
    Array.sort(arr);
    subsetWithDup(0, arr, path, result);
    return result;
}

void subsetWithDup(int index, int[] arr, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result){
    if (index == arr.length) return;
    for (int i = index; i < arr.length; i++){
        if (i != index && arr[i] == arr[i-1]) 
            continue;
        path.add(arr[i]);
        result.add(new ArrayList<Integer>(path));
        subsetWithDup(index + 1, arr, path, result);
        path.remove(path.size()-1);
    }
}

一些其他解法,无重复

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        return subsets_2(S);
    }
    
    public List<List<Integer>> subsets_1(int[] S) {
        Arrays.sort(S);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        subsetsRe(S, 0, path, res);
        return res;
    }
    void subsetsRe(int[] S, int start, List<Integer> path, List<List<Integer>> res) {
        List<Integer> sub = new ArrayList<Integer>(path);
        res.add(sub);
        for (int i = start; i < S.length; ++i) {
            path.add(S[i]);
            subsetsRe(S, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
    
    public List<List<Integer>> subsets_2(int[] S) {
        Arrays.sort(S);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        for (int i = 0; i < S.length; ++i) {
            int sz = res.size();
            for (int j = 0; j < sz; ++j) {
                List<Integer> path = new ArrayList<Integer>(res.get(j));
                path.add(S[i]);
                res.add(path);
            }
        }
        return res;
    }
}

其他解法:有重复

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] S) {
        Arrays.sort(S);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        int presz = 0;
        for (int i = 0; i < S.length; ++i) {
            int sz = res.size();
            for (int j = 0; j < sz; ++j) {
                if (i == 0 || S[i] != S[i-1] || j >= presz) {
                    List<Integer> path = new ArrayList<Integer>(res.get(j));
                    path.add(S[i]);
                    res.add(path);
                }
            }
            presz = sz;
        }
        return res;
    }
}