[LeetCode] 78. Subsets

Posted on | In

Problem

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Explanation 1

  1. We can use backtracking to solve this problem.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
                                        +-----> "1 2" +----->"1 2 3"
                                    |
           +--------> " 1 "+--------+
           |                        +-----> "1 3"
           |
 " "+---------------> " 2 "+-------> "2 3"
           |
           |
           |
           +--------> " 3 "

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    void helper(int[] nums, int start, List<List<Integer>> res, List<Integer> cur) {
        res.add(new ArrayList<Integer>(cur));

        for (int i = start; i < nums.length; i++) {
            cur.add(nums[i]);
            helper(nums, i+1, res, cur);
            cur.remove(cur.size()-1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        List<Integer> cur = new ArrayList<>();
        helper(nums, 0, res, cur);
        return res;
    }
}

Explanation 2

  1. When we iterate, we can either not choose the current number or choose the current number.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
                                     +------->" "
                     +---->" "+--+
                     |           +------->"3"
      +------>" "+---+
      |              +---->"2"+--+------->"2"
 " "+-+                          |
      |                          +-------->"23"
      |
      |                           +----->"1"
      +              +---->"1"+---+
       ------>"1"+---+            +----->"13"
                     |
                     +---->"12"+---+----->"12"
                                   |
                                   +----->"123"

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    void helper(int[] nums, int start, List<List<Integer>> res, List<Integer> cur) {
        if (start == nums.length) {
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        helper(nums, start+1, res, cur);

        cur.add(nums[start]);
        helper(nums, start+1, res, cur);
        cur.remove(cur.size()-1);
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        List<Integer> cur = new ArrayList<>();
        helper(nums, 0, res, cur);
        return res;
    }
}

Explanation 3

  1. Recursive method.
1
2
3
4
5
6
7
8
solve([1, 2, 3]):
    extract 1 out, solve([2, 3]):
        extract 2 out, solve([3]):
            extract 3 out, solve([]):
                return [[]]
            append 3: [[], [3]]
        append 2: [[], [3], [2], [3, 2]]
    append 1: [[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]]

Solution 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    void helper(int[] nums, int idx, List<List<Integer>> res) {
        if (idx == nums.length) {
            res.add(new ArrayList<Integer>());
        } else {
            helper(nums, idx+1, res);
            int n = res.size();
            for (int i = 0; i < n; i++) {
                List<Integer> cur = new ArrayList<>(res.get(i));
                cur.add(nums[idx]);
                res.add(cur);
            }
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        helper(nums, 0, res);
        return res;
    }
}

Explanation 4

  1. Iterative method.
1
2
3
4
init: [[]]
index0: [[], [1]]
index1: [[],[1],[2],[1,2]]
index2: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<Integer>());
        for (int i = 0; i < nums.length; i++) {
            int n = res.size();
            for (int j = 0; j < n; j++) {
                List<Integer> cur = new ArrayList<>(res.get(j));
                cur.add(nums[i]);
                res.add(cur);
            }
        }
        return res;
    }
}