# Subsets - Backtracking / Additional Practices

When I drew the tree, I realized it’s the same as Combination Sum but we have to add internal nodes.

Alternative to solution 2 presented, we can simply remove “return” from solution to Combination Sum:
def subsets(nums: List[int]) → List[List[int]]:
def dfs(curr_i, subset, res):
if subset:
res.append(subset.copy())
for i in range(curr_i, len(nums)):
subset.append(nums[i])
dfs(i+1, subset, res)
subset.pop()
res = []
dfs(0, [], res)
return res

Why is the exiting condition i == nums.size() ? Wouldn’t that mean the subset would only added to res when the the subset has all the elements? How would it the subset without all the elements be added to the res?

the time complexity should be n*2^n

Why is that? In solution 1 we have State-space binary tree that have 2^(n+1)-1 nodes count. Keeping in mind that DFS time complexity is O(nodes) we assume that solution 1 have Tx = O(2^n), where n is nums count. We know that solution 2 is better that solution 1 by nodes count therefore solution 2 have time complexity not worse than O(2^n)

In the C# main function there is an error, the line result.Sort(); throws the following exception.
System.InvalidOperationException: ‘Failed to compare two elements in the array.’
If I eliminate that line, my code passes the tests.

Found an alternative solution

we can assume each subsets start from 0 element, 1 elements, … len(nums)

I use logic from the permutation problem before but to avoid duplication, we look only to the next element, ignore the smaller index

here is my code

def subsets(nums: List[int]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
def dfs(start_idx: int, paths: List[int], res: List[List[int]], desired: int):
if len(paths) == desired:
res.append(paths.copy())
return

``````    if start_idx == len(nums):
return

i = start_idx

while i < len(nums):
paths.append(nums[i])
dfs(i+1, paths, res, desired)
paths.pop()
i += 1

return

res = []

for desired in range (len(nums) + 1):
dfs(0, [], res, desired)

return res
``````

def subsets(nums: List[int]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
res=[[]]
sub(res,nums,[])
return res
def sub(res,nums,path):
if len(path)!=0:
res.append(path[:])

``````for x in range(0,len(nums)):
path.append(nums[x])
sub(res,nums[x+1:],path)
path.pop()
return res
``````

Found a different solution:
def subsets(nums: List[int]) → List[List[int]]:

``````def subsets_helper(numbers, path=[]):

if len(nums) == len(path):
return

for i in range(len(numbers)):
number = numbers[i]
path.append(numbers[i])
subsets_helper(numbers[i+1:], path)
path.pop()

subsets_helper(nums)
``````

In both solutions (original and alternative) “dfs” function called the same amount of times. could you please explain the optimization?

original solution has 22^N - 1 = 22^3 - 1 = 15 nodes so 15 dfs calls

alternative solution has 2^N = 2^3 = 8 nodes so 8 dfs calls. The 2^N is the same but about half the calls.

How though? I counted in the calls in a static variables and both implementations result in exactly the same count.

I believe the time complexity for solution 2 is incorrect because of the implementation. Concatenating an item to a list(i.e. cur + [nums[i]]) is in this case going to be an O(n) operation, which means that your complexity would be O(n*2^n). Had you appended to that list in-place and then popped afterwards, it would have been O(2^n)

Clean Soloution

``````public static List<List<Integer>> subsets(List<Integer> nums) {
// WRITE YOUR BRILLIANT CODE HERE
List<List<Integer>> result = new ArrayList();
dfs(result,nums,new ArrayList<Integer>(), 0);
return result;
}
private static void dfs(List<List<Integer>> result, List<Integer> nums, List<Integer> current,int index){
if(index > nums.size()){
return;
}
for(int i = index; i < nums.size(); i++){
dfs(result,nums,current,i + 1);
current.remove(current.size() - 1);
}
}
``````

Both solutions return 15 dfs calls. If the second solution should make 8 dfs calls, then the posted solution is incorrect.

The 2nd solution I think still traversing both `include` & `exclude` option and only move the append operation(see the 2 DFS call).

Instead of doing that we should traverse the remaining option. example

``````def subsets(nums: List[int]) -> List[List[int]]:
n = len(nums)

res = []
def dfs(i, path):
if i > n:
return

res.append(path)
for x in range(i, n):
dfs(x+1, path + [nums[x]])

dfs(0, [])
return res
``````

hope the code formatting works Not backtracking but maybe something useful for everyone ``````def subsets(nums: List[int]) -> List[List[int]]:
output = helper(nums)
return output

def helper(nums):
if len(nums) == 0:
return [[]]

num = nums
subsets_without_num = helper(nums[1:])
subsets_with_num = []

for subset in subsets_without_num:
subsets_with_num.append([num] + subset)

return subsets_without_num + subsets_with_num
``````

Guys, my python solution seems easier - is it actually correct though?

``````def subsets(nums: List[int]) -> List[List[int]]:
result = [[]]

for num in nums:
for r in list(result):
result.append(r + [num])

return result
``````

Bro you should apply dfs for this problem :think:

yes, this is the iterative solution 