排列组合（遍历）回溯法

这里有一个回溯函数，使用第一个整数的索引作为参数 backtrack(first)。

1，如果第一个整数有索引 n，意味着当前排列已完成。

2，遍历索引 first 到索引 n-1 的所有整数 ，则：

在排列中放置第 i 个整数，即 swap(nums[first], nums[i])
继续生成从第 i 个整数开始的所有排列：backtrack(first +1)
现在回溯，通过 swap(nums[first], nums[i]) 还原。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # if all integers are used up
            if first == n: 
                output.append(nums[:])
            for i in range(first, n):
                # place i-th integer first
                # in the current permutation
                nums[first], nums[i] = nums[i], nums[first]
                # use next integers to complete the permutations
                backtrack(first + 1)
                # backtrack
                nums[first], nums[i] = nums[i], nums[first]
         
        n = len(nums)
        output = []
        backtrack()
        return output

class solution:
    def solvepermutation(self, array):
        self.helper(array, [])
 
    def helper(self, array, solution):
        if len(array) == 0:
            print(solution)
            return
        for i in range(len(array)):
            newarray = array[:i] + array[i + 1:]  # 删除书本
            newsolution = solution + [array[i]]  # 加入新书
            self.helper(newarray, newsolution)  # 寻找剩余对象的排列组合
solution().solvepermutation(["红", "黄", "蓝", "绿"])

li = ['A', 'B', 'C', 'D']
def solutoin(li):
    import itertools
    res = list(itertools.permutations(li))
    return len(res)

例题：
小明想上两门选修课，他有四种选择：A微积分，B音乐，C烹饪，D设计，小明一共有多少种不同的选课组合？

li = ['A', 'B', 'C', 'D']
def solutoin(li):
    import itertools
    res = list(itertools.permutations(li, 2))
    return len(res)

class solution():
    def solvecombination(self, array, n):
        self.helper(array, n, [])
 
    def helper(self, array, n, solution):
        if len(solution) == n:
            print(solution)
            return
        for i in range(len(array)):
            newarray = array[i + 1:]  # 创建新的课程列表，更新列表，即选过的课程不能再选
            newsolution = solution + [array[i]]  # 将科目加入新的列表组合
            self.helper(newarray, n, newsolution)
 
 
solution().solvecombination(["A", "B", "C", "D"], 2)