Subsets

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

    Note: The solution set must not contain duplicate subsets.

    For example,
    If nums = , a solution is:

    1. [1] -> [1, 2] -> [1, 2, 3]
    2. [2] -> [2, 3]
    3. [3]

    将上述过程转化为代码即为对数组遍历，每一轮都保存之前的结果并将其依次加入到最终返回结果中。

    Iterative

    Python

    1. class Solution:
    2.     """
    3.     @param S: The set of numbers.
    4.     @return: A list of lists. See example.
    5.     """
    6.     def subsets(self, S):
    7.         if not S:
    8.             return []
    9.         S.sort()
    10.         n = len(S)
    11.         # 000 -> []
    12.         # 001 -> [1]
    13.         # 010 -> [2]
    14.         # ...
    15.         # 111 -> [1, 2, 3]
    16.         for i in xrange(2**n):
    17.             tmp = []
    18.             for j in xrange(n):
    19.                 if i & (1 << j):
    20.                     tmp.append(S[j])
    21.             ret.append(tmp)
    22.         return ret

    利用类似bit map的原理， 将 0 ~ 2^n - 1个数值map到每个index上，如果index数值为1，就将该number加入。比如输入是[1 ,2 ,3], 那么当时，0也就是000， 那么000 -> []； 当i = 1时， 001 -> [1]; 直到i = 7, 111 -> [1, 2, 3].

    Recursive

    Python

    less code style

    1. class Solution:
    2.     """
    3.     @param S: The set of numbers.
    4.     @return: A list of lists. See example.
    5.     """
    6.     def subsets(self, S):
    7.         ret = []
    8.         self.helper(sorted(S), ret, [])
    9.         return ret
    11.     def helper(self, vals, ret, tmp):
    12.         ret.append(tmp[:])
    13.         for i, val in enumerate(vals):

    Java

    1. public class Solution {
    2.     public List<List<Integer>> subsets(int[] nums) {
    3.         List<List<Integer>> result = new ArrayList<List<Integer>>();
    4.         List<Integer> list = new ArrayList<Integer>();
    5.         if (nums == null || nums.length == 0) {
    6.             return result;
    7.         }
    10.         dfs(nums, 0, list, result);
    12.         return result;
    13.     }
    15.     private void dfs(int[] nums, int pos, List<Integer> list,
    16.                      List<List<Integer>> ret) {
    18.         // add temp result first
    19.         ret.add(new ArrayList<Integer>(list));
    21.         for (int i = pos; i < nums.length; i++) {
    22.             list.add(nums[i]);
    23.             dfs(nums, i + 1, list, ret);
    24.             list.remove(list.size() - 1);
    25.         }
    26.     }
    27. }

    源码分析

    Java 和 Python 的代码中在将临时list 添加到最终结果时新生成了对象，(Python 使用[] +), 否则最终返回结果将随着list 的变化而变化。

    回溯法可用图示和函数运行的堆栈图来理解，强烈建议使用图形和递归的思想分析，以数组[1, 2, 3]进行分析。下图所示为list及result动态变化的过程，箭头向下表示list.add及result.add操作，箭头向上表示list.remove操作。

    对原有数组排序，时间复杂度近似为 O(n \log n). 状态数为所有可能的组合数 O(2^n), 生成每个状态所需的时间复杂度近似为 O(1), 如[1] -> [1, 2], 故总的时间复杂度近似为 O(2^n).