/ Data Structure and Algorithms  

Leetcode 78. Subsets

Question



Return all subsets of a set of distinct integers.

Similar Questions

Solution - Iteration

First consider all subset of 1 element of the given array, then all subset of 2 elements of the array … and finally all subset of n elements of the array. To find all subset of k elements, just add nums[k] to all subset of k-1 element.

For example, the iteration process of nums[1, 2, 3].

1
2
3
4
initialize empty list:      []
1st iteration (nums[k] = 1):[[], [1]]
2nd iteration (nums[k] = 2):[[], [1], [2], [1, 2]]
3rd iteration (nums[k] = 3):[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// result list
List<List<Integer>> results = new ArrayList<>();

// add empty list
results.add(new ArrayList<>());

for (int num : nums) {
    // append nums[i] to all existing list
    List<List<Integer>> temp = new ArrayList<>();

    for (List<Integer> existResult : results) {
        List<Integer> tempResult = new ArrayList<>(existResult);
        tempResult.add(num);

        temp.add(tempResult);
    }

    results.addAll(temp);
}

return results;

Other solutions: backtracking
Other solutions: bit manipulation