Austin's SWE Notes 😭

    Combination, Permutation And Subset

    Difference between combination sum, subset and permutation algorithm wise and the way they handle duplication

    Combination sum and subset has a similar algorithm, permutation is a bit different since it allows different order. 

    For example, in permutation we can have

    [2,2,1], [1,2,2]

    in our result, but subset and combination sum don't allow this.

    • For combination sum and subset, we need to use a for j in range(index, len(nums)) loop to only choose the next number on the right (therefore not reusing the number that we've already used)
    • For permutation, we need to use a for num in nums loop and check if num not in tmp because we can choose any number

    Duplication handling

    For combination sum and subset, because we're using for loop, duplication handling is a bit different

    if j > index and nums[j] == nums[j - 1]: continue

    [!note]
    Duplication handling for combination sum might requires us to sort. It's just because the nature of the question

    So we skip the element from the left (we've already used) if and only if it's on the right handside of the tree (happens when j > index as when j == index we're building the left handside of the tree

    In permutation we have to use a Counter to keep track of how many numbers we are allowed to use and loop through that Counter instead.  For example

    for num in numsFrequency:  
    if numsFrequency.get(num) <= 0: continue
    ← Combination Sum
    Generate Parentheses →