Teaching Kids Programming – Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search)


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:
Input: nums = [0]
Output: [[],[0]]

Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search)

For each number, we have two choices: include or skip it in the subset.

Thus, the total number of subsets is tex_7da98591b3d78eeec743ae932ec8bcb8 Teaching Kids Programming - Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search) algorithms Combinatoric Mathematics DFS math python recursive teaching kids programming youtube video for N unique elements. The following Python Recursion is easy to understand. It takes two parameters: the current subset and the i-th number we are looking at now. So the terminal condition of Recursion is that: when we reach the end (running out of numbers), we have one subset which we can copy to the list of answers. Otherwise, we have two choices: include this number or skip it. And we can call the Recursion (backtracking) respectively.

As the Python uses Object-References when passing parameters, the list (mutable) is passed by References, we need to make a deep copy (using copy.deepcopy(cur) or cur[:]) to copy the current subset e.g. cur to answer (list of all subsets).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsets(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = []
        
        def dfs(cur, i):
            if i == n:
                # cur[:] means a copy (deep clone) or cur
                ans.append(cur[:])
                return
            # pick nums[i]
            dfs(cur + [nums[i]], i + 1)
            # skip nums[i]
            dfs(cur, i + 1)
        
        dfs([], 0)
        return ans
class Solution:
    def subsets(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = []
        
        def dfs(cur, i):
            if i == n:
                # cur[:] means a copy (deep clone) or cur
                ans.append(cur[:])
                return
            # pick nums[i]
            dfs(cur + [nums[i]], i + 1)
            # skip nums[i]
            dfs(cur, i + 1)
        
        dfs([], 0)
        return ans

The time complexity is O(2^N).

Subsets Algorithms

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
584 words
Last Post: Teaching Kids Programming - Find the Difference of Two Arrays (via Hash Set)
Next Post: Teaching Kids Programming - Finding All Subsets by Bitmasking Algorithm

The Permanent URL is: Teaching Kids Programming – Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search)

Leave a Reply