Subsets

题目描述

Given a set of distinct integers, nums, 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 nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题方法

要求non-descending,所以我们再生成subset之前应该将原list sort一下，这样后面才可以方便的处理，包括去掉重复的数的操作也会更方便

subsets的不同顺序是相同subsets,这里是non-descending，是规定了一种顺序

将结果的顺序重新调整一下，应该是

[
    [],
    [1],
    [2],
    [3],
    [1,2],
    [1,3],
    [1,2,3],
    [2,3]
]

DFS + 递归

可以看出前后subset之间的关系，我们可以用类似dfs的方法做，对当前的List将下一个num加进去进行dfs, 得到所有的subsets,然后再pop掉，对下一个num进行DFS

iterative

其实一共有2^n个子集

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
     ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();
     res.add(new ArrayList<Integer>());
     if(S == null || S.length == 0)
        return res;
    Arrays.sort(S);
    for(int i=0;i<S.length;i++)
    {
        int size = res.size();
        for(int j=0;j<size;j++)
        {
            ArrayList<Integer> item = new ArrayList<Integer>(res.get(j));
            item.add(S[i]);
            res.add(item);
        }
    }
    return res;
}

Solution

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        if not nums:
            return [[]]
        nums.sort()
        self.subsetsHelper(results, nums, 0, [])
        return results

    def subsetsHelper(self, results, nums, index, curList):
        tmpList = list(curList)
        results.append(tmpList)

        for i in range(index, len(nums)):
            curList.append(nums[i])
            #dfs
            self.subsetsHelper(results, nums, i + 1, curList)
            #pop, dfs for next number
            curList.pop()

leetcode分类总结