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=[1,2,3], a solution is:

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

由于题目要求子集合中数字的顺序是非降序排列的，所有我们需要预处理，先给输入数组排序，然后一位一位的往上叠加，比如对于题目中给的例子[1,2,3]来说，最开始是空集，那么我们现在要处理1，就在空集上加1，为[1]，现在我们有两个自己[]和[1]，下面我们来处理2，我们在之前的子集基础上，每个都加个2，可以分别得到[2]，[1, 2]，那么现在所有的子集合为[], [1], [2], [1, 2]，同理处理3的情况可得[3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了

错误！！！加进去l的时候，更改了（覆盖）原来的［］result返回［［1］，［1］］

Python 2.7.12 (default, Jun 29 2016, 14:05:02)
[GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> result = [[]]
>>> l=result[0]
>>> l
[]
>>> l.append(1)
>>> result.append(l)
>>> result
[[1], [1]]
>>>

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums) 
        result = [[]]
        for num in nums:
            for l in result:
                l.append(num)
                result.append(l)
        return result

#正确
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        result = [[]]
        for num in nums:
            result += [item+[num] for item in result]
        return result

http://joebergantine.com/articles/python-deep-copy-list-lists/

下面来看递归的解法，相当于一种深度优先搜索，参见网友JustDoIt的博客，由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

                        []        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in xrange(index, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

// 递归：实现方式，一种实现DFS算法的一种方式
class Solution {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();

        if (nums == null) {
            return results;
        }

        if (nums.length == 0) {
            results.add(new ArrayList<Integer>());
            return results;
        }

        Arrays.sort(nums);
        helper(new ArrayList<Integer>(), nums, 0, results);
        return results;
    }


    // 递归三要素
    // 1. 递归的定义：在 Nums 中找到所有以 subset 开头的的集合，并放到 results
    private void helper(ArrayList<Integer> subset,
                        int[] nums,
                        int startIndex,
                        ArrayList<ArrayList<Integer>> results) {
        // 2. 递归的拆解
        // deep copy
        // results.add(subset);
        results.add(new ArrayList<Integer>(subset));

        for (int i = startIndex; i < nums.length; i++) {
            // [1] -> [1,2]
            subset.add(nums[i]);
            // 寻找所有以 [1,2] 开头的集合，并扔到 results
            helper(subset, nums, i + 1, results);
            // [1,2] -> [1]  回溯
            subset.remove(subset.size() - 1);
        }

        // 3. 递归的出口
        // return;
    }
}

http://www.cnblogs.com/TenosDoIt/p/3451902.html

what is difference between + and append?

"+"必须两个类型相同，不能int＋list

"+" 和extend一样

>>> c = [1, 2, 3]
>>> c
[1, 2, 3]
>>> c += c
>>> c
[1, 2, 3, 1, 2, 3]
>>> c = [1, 2, 3]
>>> c.append(c)
>>> c
[1, 2, 3, [...]]
>>> c = [1, 2, 3]
>>> c.extend(c)
>>> c
[1, 2, 3, 1, 2, 3]

>>> a = [1, 2, 3]
>>> a + 4
Traceback (most recent call last):
  File "<pyshell#13>", line 1, in <module>
    a + 4
TypeError: can only concatenate list (not "int") to list
>>> a + [4]
[1, 2, 3, 4]
>>> a.append([4])
>>> a
[1, 2, 3, [4]]
>>> a.extend([4])
>>> a
[1, 2, 3, [4], 4]

What is the difference between:

some_list1 = []
some_list1.append("something")

and

some_list2 = []
some_list2 += ["something"]

the only difference is performance: append is twice as fast.