Are there any constraints on the size of the input array? This helps determine if we need to worry about exceeding memory limits or if we can optimize for specific input sizes.
Can the array contain duplicate elements? This will influence our approach to avoid generating duplicate subsets.
Is the order of subsets in the output important? This tells us if we need to maintain a specific order or if any order is acceptable.
Should I consider an empty array as valid input? This clarifies an edge case we need to handle.
Thought Process
Understanding the Problem: We need to generate all unique combinations of elements from a given set. This is essentially finding the power set.
Identifying Potential Approaches:
Brute Force: Generate all possible combinations by trying every possible inclusion/exclusion of each element. This might involve nested loops or recursive calls.
Optimized: We can use a more elegant recursive approach (backtracking) to systematically explore the combinations, potentially reducing redundant computations.
Code {#code}
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def helpers(S, i, slate):
#Base Case: No more elements left to be considered
if i == len(S): # The partial solution is the next subset, to be appended to the result
result.append(slate[:])
# Recursive Case: S[i] is the next element to examine
else:
slate.append(S[i])
helpers(S, i+1, slate) #delegate the rest of the work to a subordinate
slate.pop()
helpers(S, i+1, slate)
helpers(nums, 0, [])
return result
Recursion Tree
Problem Solving Patterns
This is fill in the blanks problem. In each blank decision has to be
made whether to include or exclude the value.
This problem is very similar to the generalized recursion
template. The recursion template assumes permutation so it has a for
loop to traverse through the array in the recursive case. This is
combination problem (making choice of whether to include or exclude
a value for a given blank). This is the only change.
There are not many alternative approaches to this other than writing
a multi for loop.
Complexity Analysis
\[\begin{eqnarray}
\text {Time Complexity} = \text{Work done by Leaf Node workers} + \\
\text{Work done by Internal Node workers}
\end{eqnarray}\]
\begin{equation}
\text{Input Space} = \text{Given array} = N
\end{equation}
\begin{equation}
\text{Output Space} = \text{Given array} = N
\end{equation}
Input Space = N
Output size = O(2^n). N/2 = O(2^N * N)
Stack Space = freeze the recursion tree at the highest point of stack space i.e N
each stack is using constant amount of space. So O(N)
Total space complexity = O(2^N.N)
Time Complexity = = 2^N.
Each leaf worker is executing work same as the length of the
slate. Whatever in slate, we are cloning the size of the slate. on
average it is n/2. O(2^N.N)
Internal node workers O2^N. Work done by internal node worker is constant. (O(1))
Total complexity is dominated by leaf leverl worker. = O(2^N.N)
Time Complexity: O(N * 2^N), where N is the length of the input array. This is because we have 2 choices (include or exclude) for each element, leading to 2^N possible subsets. We also perform O(N) operations to copy each subset into the result.
Space Complexity: O(2^N) in the worst case to store all the subsets in the result list. The recursion depth can also reach O(N) in the worst case, contributing to the space complexity.
### 2. [Permutations - LC 46 - Medium](https://leetcode.com/problems/permutations/) {#2-dot-permutations-lc-46-medium}
<div class="plantuml">
</div>
#### Code {#code}
```python
class Solution:
. def permute(self, nums: List[int]) -> List[List[int]]:
results = []
def helper(s, i, slate):
#Base Case
if i == len(s):
results.append(slate[:])
#Recursive Case
else:
for c in range(i, len(s)):
# For permutation problems, we have to swap the choice and
# swap it back after the recursive call !!!IMPORTANT!!!
s[c], s[i] = s[i], s[c]
slate.append(s[i])
helper(s, i+1, slate)
slate.pop()
s[c],s[i] = s[i], s[c]
return results
helper(nums, 0, [])
return results
Recursion Tree
Multiple choices and the number of choices come down. result in loop
Different form include/exclude of combination problems
Since any choice can be picked, it means any index. how to pass the
contiguous data down…so swap first and then pass it down
Remember to swap it back… if not, somewhere down it may end up in
same perumtation and the final result will be missing some other
permutations.
The need for swapping is a permutation specific issue because of the
need for passing continous array
Space Input + Aux + output
input = O(N) aux = O(N) output = O(N!*N)
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
def helper(S, i, slate):
if i == len(S):
result.append(slate[:])
else:
count = 1
j = i+1
while j <= len(S) - 1 and S[i] == S[j]:
count += 1
j += 1
for copies in range(0, count+1):
for op in range(copies):
slate.append(S[i])
helper(S, i+count, slate)
for op in range(copies):
slate.pop()
helper(nums, 0, [])
return result
Recursion Tree
Coding Mistakes
2022-02-27: 😟 😟 😞
❌ Forgot to sort the array. ( we should get the duplicate numbers
together before we can process the subsets)
❌ Array overflow. While j <= len(array) should have been j <=
len(array) - 1
❌ for copies in range(0, count+1): I have to always end the range to count+1 and not count.
from typing import List
def letterCombinations(digits: str) -> List[str]:
result = []
hmap = {"2": ['a','b','c'], "3": ['d','e','f'],"4": ['g','h','i'],"5": ['j','k','l'],"6": ['m','n','o'],
"7": ['p','q','r', 's'],"8": ['t','u','v'],"9": ['w','x','y', 'z']}
def helper(digitstr, i, slate):
#Base Case if there is no more string, then return
if i == len(digitstr):
if len(slate) > 0:
result.append("".join(slate))
# Recursive Case ....process each letter
else:
for letter in hmap[digitstr[i]]:
slate.append(letter)
helper(digitstr, i+1, slate)
slate.pop()
helper(digits, 0, [])
return result
print(letterCombinations("234"))
Coding Mistakes
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
result = []
hmap = {'2':'abc','3':'def', '4':'ghi', '5':'jkl',
'6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
def helper(s, i, slate):
if len(s) == i:
if len(slate):
result.append("".join(slate))
return
#Recursive Case:
for j in hmap[s[i]]:
slate.append(j)
helper(s, i+1, slate)
slate.pop()
helper(digits, 0, [])
return result
2022-02-28: 😟 😞
Major mistake. Forgot the logic for the for loop. Instead of
looping through the digit string, I looped through the hashmap.
for letter in hmap[digits[i]]: # correct way
for letter in hmap[i]: # WRONG
In the base case, I should not blindly append the slate to the
result. I need to check if the index is > 0. This is because if the
input is empty string, it is added to the result. In this case, it
should be empty result list.
Silly error - Missed semicolon at the end of function definition.
def generate_palindromic_decompositions(s):
"""
Args:
s(str)
Returns:
list_str
"""
# Write your code here.
# Input validation
if not s or len(s) == 1:
return [s]
result = []
def palindromic_decomposition(s, index, slate):
# base case
if index == len(s):
result.append('|'.join(slate))
return
# Recursive Case
# take every possible string from the current position and if it's palndromic go forward, and if it's not prune
for i in range(index+1, len(s)+1):
substring = s[index:i]
if is_palindrome(substring):
slate.append(substring)
palindromic_decomposition(s, i, slate)
# at the end of dfs remove what was appended to
slate.pop()
palindromic_decomposition(s, 0,[])
return result
def is_palindrome(string):
if not string or len(string) == 1: return True
start, end = 0, len(string)-1
while start < end:
if string[start] != string[end]:
return False
start += 1
end -= 1
return True
def check_if_sum_possible(arr, k):
def helper(arr, i, slate,k):
sum = 0
for i in range(len(slate)):
sum += slate[i]
if sum == k:
return True
# Base Case:
if i == len(arr):
return False
# Recursive Case:
helper(arr, i+1, slate,k)
slate.append(arr[i])
helper(arr, i + 1, slate,k)
slate.pop()
status = helper(arr, 0, [], k)
return status
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
def helper(left, right, slate):
if left > right:
return
#Base Case
if left == 0 and right == 0:
result.append("".join(slate))
return
#Recursive Case
else:
if left > 0:
slate.append('(')
helper(left-1, right, slate)
slate.pop()
if right > 0:
slate.append(')')
helper(left, right-1, slate)
slate.pop()
helper(n, n, [])
return result
Complexity Analysis
Coding Mistakes
2022-02-27: 😞
I could not initially recollect that in this problem, we need to
approach from both left and right side.
Missed adding node.val to slate for base case
Run time error for case error while referencing targetSum as
targetsum.
Compilation error for missing out the function keyword 'def'
before the helper function
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
def helper(n, i, slate):
#Backtracking
if len(slate) == k:
result.append(slate[:])
return result
#Base Case
if i >= n+1:
return
#Recursive Case
else:
helper(n, i+1, slate)
slate.append(i)
helper(n, i+1, slate)
slate.pop()
helper(n, 1, [])
return result
ChecklistWhat
Is this a combinatorial enumeration problem?
If so, what are the blanks?
How many blanks to be filled?
With what are they to be filled?
is the logic applied on index?
is the logic applied on the input array?
is the logic applied on the output slate?
At what stage is this applied? while backtracking? or while invoking the recursive function
How
Does Pre sorting help?
Does multiple passes help?
Does sliding window help?
Does two or three pointers help?
Does saving values to hashmap help?
Does DFS or BFS help?
Does Backtracking required?
Patterns:
No change to the standard recursion template - Permutations, Subsets
Addition of backtracking rest everything same - Combinations, Target sums up to K (IK problem)
Change to input - Generate Parenthesis
Change to index - Subset II, Permutations II
Transformation of input in recursive case - Letter case permutation, Letter case to phone combination
Extra functions and validations - Palindromic decomposition of string
When no changes to the input string, no need for two recursive calls - Letter case permutation, Letter combination problems
With mutable approach, leaf level always does the cloning, so focus
on them for total compelxity. internal worker only adds to the slate…so contstant amortized time
In a complete binary tree, the number of leaf nodes is equal to the number of internal nodes excluding the 1. 50% of nodes are leaf nodes.
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort()
def helper(S, i, target, slate):
#Backtrack
if target < sum(slate):
return
# Add result to global bag and return
if target == sum(slate):
result.append(slate[:])
return
#Base Case
if i == len(S):
return
#Recursive Case
#Count duplicates and include/exclude equal to duplicate count
count = 1
j = i+1
while j <= len(S) - 1 and S[i] == S[j]:
count += 1
j += 1
for copies in range(0, count+1):
for op in range(copies):
slate.append(S[i])
helper(S, i+count,target, slate)
for op in range(copies):
slate.pop()
helper(candidates, 0,target, [])
return result
