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]]:
answer = []
def subsets_helper(numbers, path=[]):
answer.append(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)
return answer
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;
}
result.add(new ArrayList(current));
for(int i = index; i < nums.size(); i++){
current.add(nums.get(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[0]
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