78. Subsets.md

78. Subsets

---

leetcode Daily Challenge on July 11th, 2020.

leetcode-cn Daily Challenge on September 20th, 2020.

---

Difficulty : Medium

Related Topics : Array、BackTracking、Bit Manipulation

---

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

---

Solution

• mine

  • Java Your runtime beats 97.15 % of java submissions. got it form discuss

    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<Integer>());
        
        List<List<Integer>> temp = new ArrayList<>();
        for(int i : S) {
            temp.clear(); 
            for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);
                temp.add(a);
            }
            res.addAll(temp);
        }
        return res;
    }
    

  • Runtime: 1 ms, faster than 65.72%, Memory Usage: 40 MB, less than 35.52% of Java online submissions

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

---

• the most votes Your runtime beats 97.15 % of java submissions. link

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
        list.add(new ArrayList<>(tempList));
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

---

• other Your runtime beats 97.15 % of java submissions.

class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<Integer>());
        
        Arrays.sort(S);
        for(int i : S) {
            List<List<Integer>> tmp = new ArrayList<>();
            for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);
                tmp.add(a);
            }
            res.addAll(tmp);
        }
        return res;
    }
}

---