LeetCode #78 Subsets

Posted on | Post modified | 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],
  []
]

Solution

Method: Backtracking

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []

        def is_a_solution(answer, kth, info):
            return kth == len(info)
        
        def process_solution(answer, kth, info):
            ret.append([val for val, flag in zip(info, answer) if flag])
        
        def construct_candidates(answer, kth, info):
            return [False, True]
        
        def backtrack(answer, kth, info):
            if is_a_solution(answer, kth, info):
                process_solution(answer, kth, info)
            else:
                kth += 1
                candidates = construct_candidates(answer, kth, info)
                for candidate in candidates:
                    answer.append(candidate)
                    backtrack(answer, kth, info)
                    answer.pop()
        
        backtrack([], 0, nums)
        
        return ret

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []

        def backtrack(answer, kth, info):
            if kth == len(info):
                ret.append([val for idx, val in enumerate(info) if answer[idx]])
            else:
                kth += 1
                candidates = [False, True]
                for candidate in candidates:
                    answer[kth - 1] = candidate
                    backtrack(answer, kth, info)
        
        backtrack([0 for _ in nums], 0, nums)
        
        return ret