leetcode 78. Subsets (3种方法）

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],

[]

]

给出一个数组，让输出所有数组中元素的组合，包含[]

思路：

每个元素可以被选或者不被选，那么一共就有2n种子集

方法1:

利用二进制数，对于input = [1, 2, 3]

对应3位的二进制数

000 001 010 011 100 101 110 111

每位的0代表元素没有被选择，1代表元素被选择，可以得到8种组合的子集

这8个2进制数对应了0～23-1, 也就是0～1<<3 (input.length)

遍历input的index，1左移index位，和每个2进制数与的结果如果是1，代表元素被选择

时间复杂度O(n * 2n)

//1ms
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
         
         if (nums == null || nums.length == 0) {
             return result;
         }
         
         int n = nums.length;
         
         for (int i = 0; i < 1 << n; i ++) {
             ArrayList<Integer> tmp = new ArrayList<>();
             for (int index = 0; index < n; index ++) {
                 if ((i & 1 << index) > 0) {
                     tmp.add(nums[index]);
                 }
             }
             result.add(tmp);
         }
         
         return result;
     }
           

方法2：

例如input = [1, 2, 3]

刚开始subset是[]

然后遍历元素，先取1，在上一步[]中append1, 而且保留上一步的subset

[1] + []

然后取2，在前两个的基础上append2，而且保留上一步的subset

[1, 2], [2] + [1], []

然后取3， 在上一步的基础上append3，且保留上一步的subset

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

所以首先保存一个[]

然后遍历input的元素，逐步在上一步的基础上append

//0ms
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<List<Integer>>();
        }
        
        int n = nums.length;
        
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        
        result.add(new ArrayList<Integer>());
            
        for (int i = 0; i < n; i ++) {
            int size = result.size();
            for (int j = 0; j < size; j++) {
                List<Integer> cur = result.get(j);
                List<Integer> tmp = new ArrayList<>(cur);
                tmp.add(nums[i]);
                result.add(tmp);
            }            
        }
        
        return result;
        
    }
           

方法3:

DFS

子集的长度从0～input.length

对每个子集的长度作combination版DFS，也就是下一次从i+1开始

注意满足长度的时候一定要建一个新的数组，而不能直接add cur，因为add cur会add它的object，而后面cur变动的时候add的元素也会跟着变动，最后全部会变成空list

if (len == cur.size()) {
        ArrayList<Integer> tmp = new ArrayList<>(cur);
        result.add(tmp);
        return;
    }
           

//1ms
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<List<Integer>>();
        }
        
        int n = nums.length;
        
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> cur = new ArrayList<Integer>();
        
            
        for (int i = 0; i <= n; i++) {
            dfs(nums, i, 0, cur, result);
        }
        
        return result;
        
    }
    
    public void dfs(int[] nums, int len, int start, List<Integer> cur, ArrayList<List<Integer>> result) {
        if (len == cur.size()) {
            ArrayList<Integer> tmp = new ArrayList<>(cur);
            result.add(tmp);
            return;
        }
        
        for (int i = start; i < nums.length; i++) {
            cur.add(nums[i]);
            dfs(nums, len, i + 1, cur, result);
            cur.remove(cur.size() - 1);
        }
    }