78. Subsets

Question:

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

Thinking:

• Method:
  • 回溯法，参考Question9_4

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        backtrace(nums, result, nums.length);
        return result;
    }
    public static void backtrace(int nums[], List<List<Integer>> result, int index){
        if(index == 0) result.add(new ArrayList<Integer>());
        else if(index < 0) return;
        else{
            backtrace(nums, result, index - 1);
            int cur = nums[index - 1];
            List<List<Integer>> copyResult = new ArrayList<>();
            for(List<Integer> l : result){
                List<Integer> copy = new ArrayList<>();
                for(Integer i : l)
                    copy.add(i);
                copy.add(cur);
                copyResult.add(copy);
            }
            result.addAll(copyResult);
        }
    }
}

二刷

这道题写了三遍了，google面试的时候就碰到这道题了，当时没写出来，现在看好简单。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums == null) return result;
        result.add(new LinkedList<>());
        backtrace(result, nums, 0);
        return result;
    }
    private void backtrace(List<List<Integer>> result, int[] nums, int index){
        if(index == nums.length)
            return;
        else{
            int size = result.size();
            for(int j = 0; j < size; j++){
                List<Integer> temp = result.get(j);
                List<Integer> t = new LinkedList<Integer>(temp);
                t.add(nums[index]);
                result.add(new LinkedList<Integer>(t));
            }
            backtrace(result, nums, index+1);
        }
    }
}

Third time

• Method 1: dfs

  class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length == 0) return result;
        dfs(result, nums, new LinkedList<Integer>(), 0);
        return result;
    }
    private void dfs(List<List<Integer>> result, int[] nums, List<Integer> temp, int index){
        result.add(new LinkedList<Integer>(temp));
        for(int i = index; i < nums.length; i++){
            temp.add(nums[i]);
            dfs(result, nums, temp, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
  }
  

Amazon session

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