Subsets

Posted on | In , , , , |

Question

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Analysis

典型的回溯。解题的时候第一想的是怎么样才是一个合适的退出条件。想到的是在长度满足的时候。就是外层循环来找特定长度的集合，这样的话指定一个长度，相当于就是回溯的出口。

这个解可以进一步简化，事实上在对每一个size回溯的时候，我们需要判断长度到达size，这时候才记录下来。事实上对于所有遍历到的值，都可以直接记录下来，这样也不用再进行一次外层size的循环。

对于这道题可以直接进行循环解。即一位位的向上叠加。思路如下，对解集合先放置一个空集合。[[]], 然后对于每新来的一个数，遍历解集合，并在解集合的元素上加上新的元素，比如，这样的一个解集合演化。[[]] —>[[], [1]] —>[[], [1], [2], [1,2]] —> [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Solution

对每个size回溯

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>& nums) {
        vector<int> ss;
        vector<vector<int> > res;
        for (int i=0; i <= nums.size(); ++i) {
            subsetsN(nums, i, 0, ss, res);
        }
        return res;
    }

    void subsetsN(vector<int> & nums, int cnt, int pos, vector<int> &ss, vector<vector<int> > &res) {
        if (ss.size() == cnt) res.push_back(ss);
        else {
            for (int i=pos; i < nums.size(); ++i) {
                ss.push_back(nums[i]);
                subsetsN(nums, cnt, i+1, ss, res);
                ss.pop_back();
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        for i in range(len(nums)+1):
            self.dfs(nums, i, 0, res, [])
        return res

    def dfs(self, nums, length, level, res, out):
        if length == 0:
            res.append(out)
            return res
        for i in range(level, len(nums)):
            if length > 0:
                self.dfs(nums, length -1, i+1, res, out + [nums[i]])

记录所有可得到的集合

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>& nums) {
        vector<int> ss;
        vector<vector<int> > res;
        //for (int i=0; i <= nums.size(); ++i) {
            subsetsN(nums, 0, ss, res);
        //}
        return res;
    }
    
    void subsetsN(vector<int> & nums,  int pos, vector<int> &ss, vector<vector<int> > &res) {
        res.push_back(ss); // push every set obtained
        //else {
            for (int i=pos; i < nums.size(); ++i) {
                ss.push_back(nums[i]);
                subsetsN(nums, i+1, ss, res);
                ss.pop_back();
            }
        //}
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [] 
        self.dfs(nums, 0, res, [])
        return res

    def dfs(self, nums, pos, res, out):
        res.append(out)
        for i in range(level, len(nums)):
            self.dfs(nums,i+1, res, out + [nums[i]])

循环直接解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> ss;
        res.push_back(ss);
        for (int i = 0; i < nums.size(); ++i) {
            int n = res.size();
            for (int j = 0; j < n; ++j) {
                vector<int> temp = res[j];
                temp.push_back(nums[i]);
                res.push_back(temp);
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        res.append([])
        for _, num in enumerate(nums):
            n = len(res)
            for i in range (n):
                out = res[i]
                out = out + [num]
                res.append(out)

        return res