78. Subsets.md

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);
        }
    }
}

C++ version

• Method 1: power set

   class Solution {
   	vector<vector<int>> res;
   	void dfs(int cur, vector<int>& nums, vector<int>& temp){
   		res.emplace_back(temp);
   		for(int i = cur; i < nums.size(); ++i){
   			temp.emplace_back(nums[i]);
   			dfs(i + 1, nums, temp);
   			temp.pop_back();
   		}
   	}
   public:
   	vector<vector<int>> subsets(vector<int>& nums) {
   		if(nums.empty()) return {};
   		vector<int> temp;
   		dfs(0, nums, temp);
   		return res;
   	}
   };