题解 |全排列系列题解

面试时被问到了，但是没刷过这方面的专项题，现在查缺补漏 回溯的经典题型 回溯其实就是按顺序枚举每一个位置出现的可能数字。以此构建一个树，叶子结点存放的就是排列组合的答案。深度优先遍历这棵树，因为要得到每个叶子结点的结果，所以每次都要回退，撤销之前的选择。使用递归。 深度优先遍历：（需要回到上一个节点） *状态变量： depth：递归到了第几层 path：选择了哪些数（栈结构） used:当前数有没有出现过

1. 全排列 给定一个不含重复数字的数组 nums ，返回所有可能的全排列 。可以 按任意顺序 返回答案。

temp:每一次的有效结果；check:标记是否被找过（0为未用过，1为用过）；self.res :保存最终结果

class Solution:
    def permute(self, nums):
    	nums.sort()
        self.res = []
        check = [0 for i in range(len(nums))]
        self.backTrack([],nums,check)
        return res
        
    def backTrack(self,temp,num,check):
    	if len(temp) == len(nums):
        	self.res.append(temp)
            return 
        for i in range(len(nums)):
        	if check[i] == 1:
            	continue
            check[i] = 1
            self.backTrack(temp + [nums[i]],nums,check)
            check[i] = 0
           

2. 全排列 II,给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

class Solution:
	def permute(self,nums):
    	nums.sort()
        self.res = []
        check = [0 for i in range(len(nums))]
        self.backTrack([],nums,check)
        return res
        
    def backTrack(self,temp,nums,check):
    	if len(temp) == len(nums):
        	self.res.append(temp)
            return
        for i in range(len(nums)):
        	if i > 0 and nums[i] == nums[i - 1] and check[i-1]==0:
            	continue
            check[i] = 1
            self.backTrack(temp + [nums[i]],nums,check)
            check[i] = 0

3.子集:给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。

class Solution:
	def subsets(self,nums):
    	if not nums:return []
    	n = len(nums)
    	res = []
    	def helper(index,temp):
        	res.append(temp)
            for i in range(index,n):
            	helper(i+1,temp+[nums[i]])
        helper(0,[])

4.子集 II:给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

class Solution:
	def subsets(self,nums):
    	if not nums:return []
    	n = len(nums)
    	res = []
        nums.sort()
    	def helper(index,temp):
        	if temp not in res:
            	res.append(temp) 
            for i in range(index,n):
            	helper(i+1,temp+[nums[i]])
        helper(0,[])
        return res

5.组合总和:给定一个无重复元素的正整数数组 nums 和一个正整数 target ，找出 nums 中所有可以使数字和为目标数 target 的唯一组合。

class Solution:
	def combineSum(self,target,nums):
    	res = []
    	def helper(target,nums,temp):
        	if target == 0:
            	res.append(temp)
            if target < 0:
            	break
            for i in range(len(nums)):
            	if nums[i] > target:
                	return 
                helper(target - nums[i],nums[i:],temp + [nums[i]])
        helper(target,nums,[])
        return res
        

6.组合总和 II:给定一个数组 nums 和一个目标数 target ，找出 nums 中所有可以使数字和为 target 的组合。nums 中的每个数字在每个组合中只能使用一次。

class Solution:
	def combineSum(self,target,nums):
    	res = []
        n = len(nums)
        nums.sort()
    	def helper(index,temp_sum,temp):
        	if target == temp_sum:
            	res.append(temp)
                return 
            for i in range(index,n):
            	if temp_sum + nums[i] > target:
                	break
                if i > index and nums[i] == nums[i+1]:
                	continue
                helper(i + 1,temp_sum + nums[i],temp + [nums[i]])
        helper(0,0,[])
        return res