算法 day29 回溯5

491 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

def backtracking(nums,startIndex,path,result):
	if startIndex>=len(nums):
		return  # if这一部分不写也可以
	if len(path)>1:
		result.append(path[:]) 
	uset=set() #每一层去重
	for i in range(startIndex,len(nums)):
		if (path and nums[i]<path[-1]) or nums[i] in uset:
			continue
		uset.add(nums[i])
		path.append(nums[i])
		backtracking(nums,i+1,path,result)
		path.pop()
def findSubseq(nums):
	result=[] #path可以不写，result一定要写，在别的函数内的result，当前函数不认，只能在当前函数中赋值将其带入到其他函数中
	backtracking(nums,0,[],result)	
	return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 细品倒数第二行

def func1(index,end,b=[]):
	for i in range(index,end):
 		b.append(i)
   
def func2():
    b=[]
    func1(3,5,[])  #a(3,5,b)
    return b
1
2
3
4
5
6
7
8

46 全排列

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

def backtracking(nums,path,used,result):
	if len(path)==len(nums):
		result.append(path[:])
		return
	for i in range(len(nums)):
		if used[i]:
			continue
			
		used[i]=True
		path.append(nums[i])
		backtracking(nums,path,used,result)
		path.pop()
		used[i]=False
def permute(nums):
	result=[]
	used=[False]*len(nums)
	backtracking(nums,[],used,result)
	return result 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

47 全排列II

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

def backtracking(nums,path,used,result):
	if len(path)==len(nums):
		result.append(path[:])
		return
	for i in range(len(nums)):
		if (i>0 and nums[i]==nums[i-1] and not used[i-1]) or used[i]: #not used[i-1]==False是对当前层去重，used[i-1]==True是对下一层去重
		# or 前面的条件是对横向的判断去重 后面的条件是对纵向的判断去重
			continue
		used[i]=True
		path.append(nums[i])
		backtracking(nums,path,used,result)
		path.pop()
		used[i]=False
1
2
3
4
5
6
7
8
9
10
11
12
13