Monday, November 17, 2014

[LeetCode] Subsets I, II

Subsets I


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],
  []
]


Subsets II

Given a collection of integers that might contain duplicates, 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,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]


思路:Subsets I

方法1:backtracking

与combination/combination sum I, II思路一样。区别在于单层扫描时不用跳过重复数字,而在进入下一层递归前就需要把当前subset压入结集中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(),S.end());
        findSubsets(S, 0, sol, allSets);
        return allSets;
    }
    
    void findSubsets(vector<int> &S, int start, vector<int> &sol, vector<vector<int>> &allSets) {
        for(int i=start; i<S.size(); i++) {
            sol.push_back(S[i]);
            allSets.push_back(sol);
            findSubsets(S, i+1, sol, allSets);
            sol.pop_back();
        }
    }
};


方法2:添加数字构建subset

起始subset集为:[]
添加S0后为:[], [S0]
添加S1后为:[], [S0], [S1], [S0, S1]
添加S2后为:[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
红色subset为每次新增的。显然规律为添加Si后,新增的subset为克隆现有的所有subset,并在它们后面都加上Si。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(), S.end());
        for(int i=0; i<S.size(); i++) {
            int n = allSets.size();
            for(int j=0; j<n; j++) {
                sol = allSets[j];
                sol.push_back(S[i]);
                allSets.push_back(sol);
            }
        }
        return allSets;
    }
};


方法3:bit manipulation

由于S[0: n-1]组成的每一个subset,可以看成是对是否包含S[i]的取舍。S[i]只有两种状态,包含在特定subset内,或不包含。所以subset的数量总共有2^n个。所以可以用0~2^n-1的二进制来表示一个subset。二进制中每个0/1表示该位置的S[i]是否包括在当前subset中。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        sort(S.begin(), S.end());
        unsigned long long maxNum = pow(2, S.size()) - 1;
        for(unsigned long long i=0; i<=maxNum; i++) 
            allSets.push_back(num2subset(S, i));
        return allSets;
    }
    
    vector<int> num2subset(vector<int> &S, unsigned long long num) {
        vector<int> sol;
        int i=0;
        while(num) {
            if(num & 1) sol.push_back(S[i]);
            num >>= 1;
            i++;
        }
        return sol;
    }
};


思路:Subsets II

和3sum, combination sum II一样的去重思路。这类问题两个细节千万不能粗心:

1. 一定要先排序
2. 调用下一层递归时(ln 17),起始index 一定是i+1而不能错写成start+1


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(), S.end());
        findSubsetsWithDup(S, 0, sol, allSets);
        return allSets;
    }
    
    void findSubsetsWithDup(vector<int> &S, int start, vector<int> &sol, vector<vector<int>> &allSets) {
        for(int i=start; i<S.size(); i++) {
            if(i>start && S[i]==S[i-1]) continue;
            sol.push_back(S[i]);
            allSets.push_back(sol);
            findSubsetsWithDup(S, i+1, sol, allSets);
            sol.pop_back();
        }
    }
};

4 comments:

  1. Replies
    1. 需要的,因为题目要求输出结果为升序排列。

      Delete
  2. subset2 中为什么要加上 i>start这个限制条件

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete