[Pattern] Search

1. Generate permutations

• DFS + loop with increasing index

def dfs(self, count, nums, s, v):
        if count == len(nums):
            self.res.append(s[:])
            return
        for i in range(len(nums)):
            if v[i]==1:
                continue
            v[i]=1
            s.append(nums[i])
           
            self.dfs(count+1,nums,s,v)
            s.pop()
            v[i] = 0

2. Generate combinations

• DFS + loop with increasing

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
def dfs(idx, s, count):
            if count == k:
                res.append(s[:])
            for i in range(idx, n):
                s.append(i+1)
                dfs(i+1, s, count+1)
                s.pop()
                
        dfs(0,[], 0)
        return res

3. Generate no repeating combinations

• Sorting + Compare current and the previous index

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        
        def dfs(idx, s):
            if idx == len(nums):
                return
            for i in range(idx, len(nums)):
                if i>idx and nums[i] == nums[i-1]:
                    continue
                s.append(nums[i])
                res.append(s[:])
                dfs(i+1, s)
                s.pop()
        
        nums.sort()
        dfs(0,[])
        return res