全排列

https://leetcode-cn.com/problems/permutations/

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        rst = []
        if nums is None or len(nums) == 0:
            return rst
        # 一种排列
        line = []
        self.helper(rst,line,nums)
        return rst
    def helper(self,rst,line,nums):
        #回溯终止条件
        if len(line) == len(nums):
            rst.append(line[:])
            return
        for i in range(len(nums)):
            # 个性化要求
            if nums[i] in line:
                continue
            # 固定模板
            line.append(nums[i])
            self.helper(rst,line,nums)
            line.pop(-1)

全排列II

https://leetcode-cn.com/problems/permutations-ii/

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        rst = []
        if nums is None or len(nums) == 0:
            return rst
        # 一种排列
        line = []
        visited = [0]*len(nums)
        nums.sort()
        self.helper(rst,line,visited,nums)
        return rst
    def helper(self,rst,line,visited, nums):
        #回溯终止条件
        if len(line) == len(nums):
            rst.append(line[:])
            return
        for i in range(len(nums)):
            # 个性化要求:访问过的或者是有相同的连着，但是跳过了前面的而访问了后面的，会造成重复。
            if visited[i] == 1 or (i != 0 and nums[i] == nums[i-1] and visited[i-1] == 0) :
                continue
            # 固定模板
            visited[i] = 1
            line.append(nums[i])
            self.helper(rst,line,visited,nums)
            line.pop(-1)
            #回溯法上下操作都是对称的
            visited[i] = 0

子集问题

https://leetcode-cn.com/problems/subsets/

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        rst = []
        if nums is None or len(nums) == 0:
            return rst
        line = []
        self.helper(rst,line,nums,0)
        return rst
    # helper加了一个pos参数，控制搜索的方向从当前元素向后
    def helper(self,rst,line,nums,pos):
        #rst 每经历一个状态都加入到rst中，因为所有搜索状态都是最后的结果
        rst.append(line[:])
        for i in range(pos,len(nums)):
            line.append(nums[i])
            self.helper(rst,line,nums,i+1)
            line.pop(-1)

子集问题II

https://leetcode-cn.com/problems/subsets-ii/

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        rst = []
        if nums is None or len(nums) == 0:
            return rst
        line = []
        nums.sort()
        self.helper(rst,line,nums,0)
        return rst
    # helper加了一个pos参数，控制搜索的方向从当前元素向后
    def helper(self,rst,line,nums,pos):
        #rst 每经历一个状态都加入到rst中，因为所有搜索状态都是最后的结果
        rst.append(line[:])
        for i in range(pos,len(nums)):
            #后一个数和前一个数相等，但前一个数还跳过去了，这不行。
            if i != pos and nums[i] == nums[i-1]:
                continue
            line.append(nums[i])
            self.helper(rst,line,nums,i+1)
            line.pop(-1)