LeetCode Subsets

原題鏈接在這里：https://leetcode.com/problems/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],[]
]

題解：

類似Permutations,?Combination Sum,Palindrome Partitioning. 都是backtracking. dfs時把現有item copy后加進res. item加上當前nums元素繼續dfs.

Time Complexity: exponential. Space: O(nums.length). stack space.

AC Java:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        dfs(nums, 0, new ArrayList<Integer>(), res);
        return res;
    }
    
    private void dfs(int [] nums, int start, List<Integer> item, List<List<Integer>> res){
        res.add(new ArrayList<Integer>(item));
        for(int i = start; i<nums.length; i++){
            item.add(nums[i]);
            dfs(nums, i+1, item, res);
            item.remove(item.size()-1);
        }
    }
}

Iteration時,?取res中現有list，每個list都加新的元素nums[i]然后再放回res中，同時保留原有list. 從[]開始一次加一個新元素。

Note: 內層for loop 的size 一定要提前提取出來，不能在內層for中現提取，因為res的size一直在變.

Time Complexity: exponential. Space: O(res.size()).

?AC Java:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0){
            return res;
        }
        //res 中加入 [] 
        res.add(new ArrayList<Integer>());
        //保證non-descending order
        Arrays.sort(nums);
        
        for(int i = 0; i<nums.length; i++){
            //這里要注意，必須提前把size提取出來，不能把提取過程直接嵌入到下面的for語句中
            //因為res的size會在下面語句中一直變化
            int size = res.size();
            for(int j = 0; j<size; j++){
                List<Integer> newItem = new ArrayList<Integer>(res.get(j));
                newItem.add(nums[i]);
                res.add(newItem);
            }
        }
        return res;
    }
}

進階題是Subsets II.