Subsets

title: Subsets tags: subset looping-through-input-and-output nested-double-for-loop backtracking include-exclude-object

Given an integer array nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

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.

Thinking Process

• Classify the problem: This is 0-1 object selection problem.
• No duplicate subsets. Any order.

Define the interface.

Input: [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Brute Force Approach

Go through two loop, start with the first element and go through the next element. 1, 2 and 3 Add 1, 1-2 and 1-3 and so on

Time and Space Complexity

T: O(N2) S: O(1)

0. For n = 0

   []

1. For n = 1

   [1] [include the output for n = 0 and [1]] [[], [1]]

2. For n = 2

   [1,2] [include the output for n = 1 and [2], [1,2]] [[], [1], [2], [1,2]]

3. n = 3

[1,2,3] [include the output for n = 0, n = 1 as well as n = 2] [[],[1],[2],[1,2], [3],[1,3],[2,3],[1,2,3]]

Generating the Subset

How do we generate the subset?

• For n = 1, build an outer list and add the subset to this list.

What should we add to the outer list?

• Inner list contains an empty list and just one element with given n.
• For n = 2
  • Add 2 to empty list.
  • Add 2 to [1].

Start with an empty set, iterate through all elements one-by-one, and add them to existing sets to create new subsets.

Solution Outline

1. Initialize the output array to an array with empty array.
2. If n = 1, add an empty array and an array with that n value to the output and return that as result. output = [[], ]
3. From n = 2 to n, traverse through the output array. Add the 2 to all the arrays inside the output array.
4. Return the output.

Iterative Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# @param {Integer[]} nums
# @return {Integer[][]}

def subsets(nums)
  output = [[]]
    
  for i in (0..nums.size-1)
    for j in (0..output.size-1)
      subset = output[j]
      output << subset + [nums[i]]
    end
  end
	
  output
end

You cannot modify the output array within the loop, so subset stores the generated element and we generate a new element and append it to the output array.

Time Complexity

In each step, the number of subsets doubles as each element is added to all the existing subsets. Therefore, there is a total of O(2 N​​) subsets, where N is the total number of elements in the input set. Since we construct a new subset from an existing set, therefore, the time complexity is O(N * 2N).

Space Complexity

The additional space is used for the output list. Since we will have a total of O(2 N) subsets and each subset can take up to O(N) space, therefore, the space complexity is O(N * 2^N).

Recursive Approach

We need a helper method: Why? Because, we need to pass the next element that we need to add to the subset.

We need to have two recursive calls in the helper. One for:

• Include
• Exclude

Unit of Work

• What is the slice of work that each recursive call must do?
• Do I need to include the element or exclude the element?
• The parent will actually control what index the child should process.

Base Case

When we reach the leaf node, I have generated one subset. It can be added to the output.

Time and Space Complexity

Time: O(N 2N) Space: O(N 2N)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# @param {Integer[]} nums
# @return {Integer[][]}
def backtrack(nums, start)
  @powerset << @subset.dup
  
  for i in (start..nums.length-1)
    @subset.push(nums[i])
    backtrack(nums, i+1)
    @subset.pop()        
  end
end

def subsets(nums)
  @powerset = [] 
  @subset = [] 
    
  backtrack(nums, 0)
    
  return @powerset
end

Refactored Solution

 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

# @param {Integer[]} nums
# @return {Integer[][]}

def wrapper(nums, index, subset, output)
  if index == nums.size
    output << subset.dup
    return
  end
        
  #include
  n = nums[index]
  subset << n
  #explore
  wrapper(nums, index+1, subset, output)
  subset.pop
    
  #exclude
  #explore
  wrapper(nums, index+1, subset, output)
end

def subsets(nums)
  output = []
  wrapper(nums, 0, [], output)
  output 
end

Alternative Solution

 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

def wrapper(chars, index, subset, output)
  if index == chars.size
    output << subset.dup
    
    return
  end
        
  #include
  wrapper(chars, index+1, subset + chars[index], output)
    
  #exclude
  wrapper(chars, index+1, subset, output)
end

def subsets(string)
  output = []
  subset = ''
  index = 0
  chars = string.chars
  wrapper(chars, index, subset, output)
  output 
end

input = "xy" 

p subsets(input)

Output: ["", “x”, “y”, “xy”]

A subset of a set S is a set that contains some or all elements of S. The subsets of a set can be found using recursion or bitwise operations.

For example, the subsets of {1, 2, 3} are {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

Java - Recursive approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

void generateSubsets(int i, int[] nums, List<Integer> curr, List<List<Integer>> subsets) {
  if (i == nums.length) {
    subsets.add(new ArrayList<>(curr));
    return;
  }
  
  curr.add(nums[i]);
  generateSubsets(i + 1, nums, curr, subsets);

  curr.remove(curr.size() - 1);
  generateSubsets(i + 1, nums, curr, subsets);
}  

C++ - Bit manipulation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

vector<vector<int>> subsets(vector<int>& nums) {
  int numSubsets = 1 << nums.size();
  vector<vector<int>> subsets;

  for (int i = 0; i < numSubsets; i++) {
    vector<int> subset;
    for (int j = 0; j < nums.size(); j++) {
      if ((i & (1 << j)) != 0) {
        subset.push_back(nums[j]);
      }
    }
    subsets.push_back(subset);
  }

  return subsets;
}

Python - Iterative approach:

1
2
3
4
5
6
7
8
9

def subsets(nums):
  subsets = [[]]

  for num in nums:
    for i in range(len(subsets)):
      curr = subsets[i]
      subsets.append(curr + [num])  

  return subsets

Finding all subsets of a set is useful for combinatorics and backtracking algorithms.

Finding all subsets of a given set is a classic problem that can be solved using a recursive approach or by using bit manipulation. Here’s a simple guide to generating all possible subsets of a set using both methods:

Method 1: Recursion

We can use a recursive function to explore all the possible subsets. We’ll choose or not choose each element and recursively call the function for the rest of the elements.

Here’s a Python code snippet to achieve this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def helper(index, current):
            if index == len(nums):
                result.append(current[:])
                return
            # Include current element
            current.append(nums[index])
            helper(index + 1, current)
            # Exclude current element
            current.pop()
            helper(index + 1, current)

        result = []
        helper(0, [])
        return result

Method 2: Bit Manipulation

Since there are (2^n) subsets of a set with (n) elements, we can use the binary representation of numbers from 0 to (2^n - 1) to represent all the subsets.

Here’s a Python code snippet for this method:

1
2
3
4
5
6
7
8

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        for i in range(1 << n):  # 2^n subsets
            subset = [nums[j] for j in range(n) if (i & (1 << j)) != 0]
            result.append(subset)
        return result

In this code snippet, (i & (1 << j)) != 0 checks if the j-th bit of i is set, which corresponds to including the j-th element of the set in the current subset.

Both of these methods have a time complexity of (O(2^n \times n)), as there are (2^n) subsets, and it takes (O(n)) time to generate each subset. The space complexity is also (O(2^n \times n)), as that’s the total size of the output.

1. Define the interface Input: [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

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

3. No duplicate subsets. Any order.

   Classify the Problem 0-1 Bounded Knapsack Problem

4. Input: [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Brute Force Go through two loop, start with the first element and go through the next element. 1, 2 and 3 Add 1, 1-2 and 1-3 and so on

   T: O(N^2) S: O(1)

5. Recursive Approach Helper method: Why? We need to pass the next element that we need to add to the subset.

6. We need to have two recursive calls in the helper

   • Include
   • Exclude

7. Unit of Work What is the slice of work that each recursive call must do? Do I need to include the element or exclude the element. The parent will actually control what index the child should process.

8. Base Case When we reach the leaf node, I have generated one subset It can be added to the output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def wrapper(nums, index)    
    if index == nums.size
       @powerset << @subset.dup
        return
    end

    # include
    element = nums[index]
    @subset << element

    # Explore
    wrapper(nums, index+1)
    @subset.delete(element)

    # exclude
    wrapper(nums, index+1)
end

def subsets(nums)
  @powerset = []
  @subset = []
  wrapper(nums, 0)
  @powerset
end

1. n = 1 [1] [[], [1]]

2. n = 2 [1,2] [include the output for n = 1 and [2], [1,2]] [[], [1], [2], [1,2]]

3. n = 3 [1,2,3] [include the output for n = 1 as well as n = 2, ] [[],[1],[2],[1,2], [3],[1,3],[2,3],[1,2,3]]

How do we generate the subset?
 - For n = 1, build an outer list and add the subset to this list
What should we add to the outer list?
 - Inner list contains an empty list and just one element with given n.        
  
  - For n = 2
    Add 2 to empty list
    Add 2 to [1]

1. Intialize the output array to an empty array.
2. If n = 1, add an empty array and an array with that n value to the output and return that as result. output = [[], ]
3. From n = 2 to n, Traverse through the output array Add the 2 to all the arrays inside the output array
4. Return the output

[1,2,3]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# @param {Integer[]} nums
# @return {Integer[][]}

def subsets(nums)
  output = [[]]

  for i in (0..nums.size-1)
    for j in (0..output.size-1)
      subset = output[j]
      output << subset + [nums[i]]
    end
  end
  output
end

1. n = 1 [1] [[], [1]]

2. n = 2 [1,2] [include the output for n = 1 and [2], [1,2]] [[], [1], [2], [1,2]]

3. n = 3 [1,2,3] [include the output for n = 1 as well as n = 2, ] [[],[1],[2],[1,2], [3],[1,3],[2,3],[1,2,3]]

How do we generate the subset?
 - For n = 1, build an outer list and add the subset to this list
What should we add to the outer list?
 - Inner list contains an empty list and just one element with given n.        
  
  - For n = 2
    Add 2 to empty list
    Add 2 to [1]

1. Intialize the output array to an empty array.
2. If n = 1, add an empty array and an array with that n value to the output and return that as result. output = [[], ]
3. From n = 2 to n, Traverse through the output array Add the 2 to all the arrays inside the output array
4. Return the output

[1,2,3]

=end

def subsets(nums) output = [[]]

for i in (0..nums.size-1)
   for j in (0..output.size-1)
      subset = output[j]
      output << subset + [nums[i]]
   end
end

return output

end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def solve(i, curr):
            if i >= len(nums):
                ans.append(curr.copy())
                return 
            curr.append(nums[i])
            solve(i+1, curr)

            curr.pop()
            solve (i+1, curr)
        solve(0,[])
        return ans

Identifying Problem Isomorphism

“Subsets” has an approximate isomorphism to “Combination Sum”.

In “Subsets”, the task is to find all possible subsets of a given set of unique integers, while in “Combination Sum” you are to find all unique combinations of a set of candidate numbers where the sum equals a target number.

The reasoning for this mapping is that both problems involve enumerating all possible combinations (subsets or sums) from a set of numbers. “Combination Sum” is a constrained version of “Subsets”, where the constraint is that the sum of the numbers in each combination must equal the target number. Thus, although not an exact isomorphism, the problems share a significant amount of structure, especially in the way they can both be solved using recursive backtracking. The strategy for “Subsets” could inform your approach to “Combination Sum”, and vice versa.

Problem Classification

This problem can be classified based on the problem domain as follows:

1. Combinatorics: The problem involves finding all possible subsets of a set, which is a basic problem in the field of combinatorics.

2. Set Theory: The concepts of subsets and power sets come from set theory. The constraint that the solution set must not contain duplicate subsets further emphasizes this aspect.

3. Array Manipulation: The input for this problem is given as an array of integers, indicating that array manipulation will be a part of the problem-solving process.

4. Constraint Satisfaction: The problem involves satisfying the specific constraint that the solution set must not contain duplicate subsets.

This classification gives an overview of the types of strategies and concepts that might be useful when approaching this problem.

Language Agnostic Coding Drills

Here are the smallest units of learning that could be separated from this piece of code, arranged in an increasing level of difficulty:

1. Defining Functions: Understand how to define a function and how to use its arguments. Recognize the importance of indentation in defining the function body.

2. Basic Data Types (Lists): Understand what a list is and how to create one. Learn about list methods like append(), copy(), and pop().

3. Conditional Statements (if): Understand the use of if statements for conditionally executing code.

4. Recursion: Understand what recursion is and how it’s used to solve problems in programming. Recognize when a problem can be solved using recursion.

5. Class Definition: Learn what a class is and how to define one in Python. Understand what a method is and how it’s defined within a class. Get to know what self refers to in a method.

6. Understanding of Python’s List Comprehensions: Learn the syntax and usage of list comprehensions for creating new lists.

7. Type Hinting: Understand how to use type hints to make your Python code more self-explanatory.

8. Problem Solving with Recursion and Backtracking: Recognize when a problem can be solved using a combination of recursion and backtracking. This involves choosing a candidate (adding an element to the current set in this case), exploring the associated subproblem (recursive function call), and then undoing the choice (removing the element from the current set).

Solution for Coding Drills in Python

Here are the Python code solutions for each of the drills listed above:

1. Defining Functions:

1
2

def say_hello(name):
    print(f"Hello, {name}!")

2. Basic Data Types (Lists):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Creating a list
my_list = [1, 2, 3, 4, 5]

# Using append() method
my_list.append(6) 

# Using copy() method
copied_list = my_list.copy() 

# Using pop() method
last_element = my_list.pop()

3. Conditional Statements (if):

1
2
3
4
5

x = 10

# If statement
if x > 5:
    print("x is greater than 5")

4. Recursion:

1
2
3
4
5
6

# Factorial using recursion
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

5. Class Definition:

1
2
3
4
5
6

class Person:
    def __init__(self, name):
        self.name = name
    
    def say_hello(self):
        print(f"Hello, my name is {self.name}")

6. Understanding of Python’s List Comprehensions:

1
2

# List comprehension to create a list of squares
squares = [x**2 for x in range(10)]

7. Type Hinting:

1
2
3

def repeat_message(message: str, times: int) -> None:
    for _ in range(times):
        print(message)

8. Problem Solving with Recursion and Backtracking:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def subsets(nums):
    ans = []

    def solve(i, curr):
        if i >= len(nums):
            ans.append(curr.copy())
            return 

        curr.append(nums[i])
        solve(i+1, curr)

        curr.pop()
        solve(i+1, curr)
    
    solve(0, [])
    return ans

# Test
print(subsets([1, 2, 3]))