题解 |全排列系列题解

最长无重复子数组

http://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4

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

全排列给定一个不含重复数字的数组 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

全排列 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