# https://leetcode-cn.com/problems/combinations/
# 77. 组合
# clarify 不能有重复组合，穷尽所有可能组合
# possible solution 回溯？！
# 
from collections import deque

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        result, queue = [], []
        def helper(start, end, num):
            # terminator
            if num == 0:
                result.append(queue[:])
                return 
            for i in range(start, end+1):
                # reduce compute
                if end - i + 1 >= num:
                    queue.append(i)
                    # dfs
                    helper(i+1, end, num-1)
                    # reverse
                    queue.pop()
        helper(1, n, k)
        return result

# https://leetcode-cn.com/problems/permutations/
# 46.全排列
# test case => [], [1], [1,2], [1,2,3]
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) <= 1:
            return [nums]
        def helper(queue, lst, res):
            if not lst:
                res.append(queue[:])
                return 
            for i, num in enumerate(lst):
                queue.append(num)
                helper(queue, lst[:i] + lst[i+1:], res)
                queue.pop() # reverse
        res = []
        helper([], nums, res)
        return res
# https://leetcode-cn.com/problems/permutations-ii/
# 47. 全排列2
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) <= 1:
            return [nums]

        def helper(queue, lst, res):
            if not lst:
                res.append(queue[:])
                return
            for i, num in enumerate(lst):
                if not i or num != lst[i-1]: # 起点一样剪枝掉
                    queue.append(num)
                    helper(queue, lst[:i]+lst[i+1:], res)
                    queue.pop()
        
        res = []
        nums.sort()
        helper([], nums, res)
        return res