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 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).

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

• Teaching Kids Programming – Finding All Subsets by Bitmasking Algorithm
• Teaching Kids Programming – Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search)
• Generate the Power SubSet using Depth First Search Algorithm
• Teaching Kids Programming – Cascading Algorithm to Find All Subsets

–EOF (The Ultimate Computing & Technology Blog) —