# Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem.

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

nums.sort()
res = [[]]
self.dfs(nums, res, [], 0)
return res

def dfs(self, nums, res, path, index):

if path not in res:
res.append(path)

for pos in range(index, len(nums)):
self.dfs(nums, res, path + [nums[pos]], pos+1)


I think the time complexity of this algorithm is: $$n \cdot n! \cdot 2^{n}$$,

My logic is as follows, we loop the array once per value i.e., $$n$$

For each loop the number of calls is $$(n-1)!$$ which is $$n!$$ complexity

Then there is a check if value in array in each call which has at most $$2^n$$ checks since thats when power set is complete but dupes are being checked

Combining them gives $$n \cdot n! \cdot 2^n$$

Is this correct?

• Can you please write proper pseudocode for a better understanding of your logic. Thanks. – Inuyasha Yagami Apr 11 at 9:14
• That is the simplest python code possible, pseduo would look exactly the same – OnePiece Apr 11 at 11:04
• If there are duplicates, why not remove the duplicate entries beforehand? Then you will not need this code part: "if path not in res: res.append(path)" – Inuyasha Yagami Apr 11 at 14:56
• And shouldn't it be $n! \cdot 2^{n}$ instead of $n \cdot n! \cdot 2^{n}$? – Inuyasha Yagami Apr 11 at 14:58
• Yes, you are correct. – Inuyasha Yagami Apr 12 at 21:03