# backtracking
    #   - time: O(2^(target/m)), m is the mim value in nums, target/m 是树的深度
    #   - space: O(target/m), m is the mim value in nums, O(target/m) 是递归时栈使用的空间（栈深度），target/m 是树的深度
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []

        def dfs(start, curSequence, curSum):
            # only consider [start, len(candidates)) from candidates
            if curSum == target:  # find a combination
                res.append(curSequence[:])  # couldn't directly use curSequence, since we still use curSequence later
                return
            if curSum > target or start >= len(candidates):  # cannot find any combination
                return

            # case 1: 包括当前 start 指向的元素
            curSequence.append(candidates[start])
            dfs(start, curSequence, curSum + candidates[start])
            curSequence.pop(-1)

            # case 2: 不包括 start 指向的元素，且 start 自增
            dfs(start + 1, curSequence, curSum)

        dfs(0, [], 0)
        return res

    # backtracking - myself
    #  - time: O(n*2^n)
    #  - space: O(n)
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()

        def dfs(start, subArray, curSum):
            if curSum == target:
                res.append(subArray[:])
                return
            if start >= len(candidates) or curSum > target:
                return

            # include candidates[start]
            subArray.append(candidates[start])
            # "start + 1", since [Each number in candidates may only be used once in the combination.]
            dfs(start + 1, subArray, curSum + candidates[start])

            # skip candidates[start] and also the candidates with the same value of candidates[start]
            subArray.pop(-1)
            start += 1
            while start <= len(candidates) - 1 and candidates[start] == candidates[start - 1]:
                start += 1
            dfs(start, subArray, curSum)

        dfs(0, [], 0)
        return res

    # backtracking - myself (逻辑有问题，虽然提交后，是完全通过的)
    #  - time: O(n!*n), n! = n * (n-1) * (n-2) ... * 1
    #     - 算法的复杂度首先受 backtrack 的调用次数制约，permute 的调用次数为 n! + n!/1! + n!/2! + n!/3! ... + n!/(n-1)! < 2n! + n!/2 + n!/2^2 + n!/2^{n-2} < 3n!
    #  - space: O(n!*n), O(n!*n) for the output list, n for calling stack (for recursion)
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []

        # base case
        if len(nums) == 1:
            return [nums[:]]

        for _ in range(len(nums)):  # run n times, time: O(n)
            n = nums.pop(0)  # remove the first element from nums
            perms = self.permute(nums)  # time: O(n!)
            for perm in perms: # time: O(n), e.g., we have [2, 3], [3, 2]. Then we are gonna add 1 into them 
                perm.append(n)
            res.extend(perms)

            nums.append(n)  # append the removed element to the end

        return res
      
      
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack(nums, 0)
        return self.res

    def backtrack(self, nums: List[int], idx: int):
        if idx == len(nums):
            self.res.append(nums[:])
            return
        for i in range(idx, len(nums)):
            nums[idx], nums[i] = nums[i], nums[idx]
            self.backtrack(nums, idx + 1)
            nums[idx], nums[i] = nums[i], nums[idx]      

# solution 1 - brute force (recursion)
# - time: O(n*2^n)??
# - space: O(n)
	def subsets(self, nums: List[int]) -> List[List[int]]:
		res = []

		def backtracking(start, curSubsets):
			# to consider the elements in nums: [start, len(nums))
			if start >= len(nums):
				res.append(curSubsets.copy())
				return

			# case 1: decision to include nums[i]
			curSubsets.append(nums[start])
			backtracking(start + 1, curSubsets)

			# case 2: decision not to include nums[i]
			curSubsets.pop(-1)
			backtracking(start + 1, curSubsets)

		backtracking(0, [])
		return res