0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Can you please write proper pseudocode for a better understanding of your logic. Thanks. $\endgroup$ – Inuyasha Yagami Apr 11 at 9:14
  • $\begingroup$ That is the simplest python code possible, pseduo would look exactly the same $\endgroup$ – OnePiece Apr 11 at 11:04
  • 1
    $\begingroup$ 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)" $\endgroup$ – Inuyasha Yagami Apr 11 at 14:56
  • 1
    $\begingroup$ And shouldn't it be $n! \cdot 2^{n}$ instead of $n \cdot n! \cdot 2^{n}$? $\endgroup$ – Inuyasha Yagami Apr 11 at 14:58
  • 1
    $\begingroup$ Yes, you are correct. $\endgroup$ – Inuyasha Yagami Apr 12 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.