面试笔试7.4(多益网络)

2018-07-04

题目：给定一个集合S（没有重复元素），输出它所有的子集

比如输入1,2,3。输出1,2,12,3,13,23,123。

思路：这道题肯定刷过，可是面试的时候死活想不起来，可能是太紧张了吧。后来找了找，果然在leetcode上找到了原题：

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

当时百度了一个很挫的解法，也没给人家面试官讲清楚，估计gg了。引以为戒！

　　这道题当时是归在了回溯法这一块，自己没有想明白，回溯法之前也是看一个大神写的，debug以后当时看懂了，但是后来再看还是**##??!! 。有幸找到了一个更容易理解的解法，就是纯数学的解法。

　　解法如下：

　　比如我们现在有一个[1,2,3]的输入数组，想要找到它的所有子集。

　　首先空集肯定是该集合的子集，所以我们初始化reslist的应该是这样的 [[]]；

　　然后，我们挑选出[1,2,3]中的第一个数1，对于这个1，我们可以选择将它加入我们的relist中，也可以不加入，如果加入，空集就会变成[1]。此时我们的reslist就变成了这样[[], [1]]；

　　接着，我们挑出第二个数2，我们同样可以将它加入我们的reslist中现有的子集中，也可以不加入。加入就会变成[2], [1,2]，而不加入则保持原有的reslist不动即[[], [1]]，所以总的可能性加起来我们能够得到的所有子集就是

[[], [1], [2], [1,2]];

　　最后，我们挑出最后一个数3，同样对于3来说，它有两个选择，要么加入到现有的集合中，要么不加入，加入就会变成[3], [1,3] ,[2,3], [1,2,3]，不加入就还是[[], [1], [2], [1,2]]，所以总的来说最后的所有可能结果集就是[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]。

代码如下：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> reslist = new ArrayList<>();
        reslist.add(new ArrayList<Integer>());
        
        for (int n : nums) { //依次选出每一个数
            int size = reslist.size();
            for (int i = 0; i < size; i++) {//遍历已经存在的list，给每一个子集添加新的数
                List<Integer> sublist = new ArrayList<>(reslist.get(i));
                sublist.add(n);
                reslist.add(sublist);
            }
        }
        
        return reslist;
    }
}