代码随想录算法训练营第三十天（回溯算法篇）|491. 非递减子序列, 46. 全排列，47. 全排列Ⅱ

491. 非递减子序列

题目链接：491. 非递减子序列 - 力扣（LeetCode）

思路

1. 判断是否将当前遍历到的元素添加到path中。

如果当前元素大于等于前一个元素，满足条件，但前提是当前的i>0，可若加上i>0，那么第一个元素就无法被加入，如果一开始就将其加入，之后又无法pop掉。于是想到比较当前path末尾和遍历到的数nums[i], 如果path存在且其末尾数大于nums[i]，就continue到后一个数再比较。那么不满足这个if条件的数就可以加到path中。

2. 如何去重。

之前是通过将nums排序后，根据当前遍历到的元素和前一个是否相同以及startIdx来去重，但无法应用到此题。这里要在for循环外面建一个set来记录当前层用过的元素，如果遍历到的元素出现在set里，就continue到下一个。

然后我又双叒陷入到回溯的漩涡当中了......我当时认为每一次在backtracking中call自己时，这个set都会被重置为空，那它是如何记录的......但事实是，每个递归层次的set是各自维护的，在运行逻辑上，会在下一层开启新的set，但当回溯时，还是能回到当前的set中的。

每一个for循环执行结束，相当于树的一层结束，每次开启新的一轮for循环时，深度就会加一，对当前的深度来说，set重开，记录当前层用过的元素。

我总是试图根据代码的逻辑一步步顺下去检验，但实在有点折磨，反而更容易被绕进去。最好直接从大框架上理解，因为回溯的每一步都是这个大框架下类似的操作。对于set来说，不要想着回溯，只看一层for循环的操作：我们要记录每一层用过的元素，所以只要它在整个for循环外被建立，每次遍历到一个元素，检验其是否在set里，若不在把它append到path中，加到set中就可。既然对一层for循环没问题，那么把放放入递归没问题。

代码实现

class Solution(object):
    def backtracking(self, nums, result, path, startIdx):
        if len(path) > 1:
            result.append(path[:])
        if startIdx == len(nums):
            return

        uset = set()
        for i in range(startIdx, len(nums)):
            if (path and nums[i] < path[-1]) or nums[i] in uset:
                continue
            path.append(nums[i])
            uset.add(nums[i])
            self.backtracking(nums, result, path, i+1)
            path.pop()

    def findSubsequences(self, nums):
        result, path = [], []
        self.backtracking(nums, result, path, 0)
        return result
        

46. 全排列

题目链接：46. 全排列 - 力扣（LeetCode）

思路

1.不需要startIdx

设定startIdx是为了不考虑之前遍历过的元素，但排列问题是有序的，比如对于数组[1,2],如果要求所有集合，得到[1,2]后，数组的第一位到了2，后面没有元素了，就直接结束，不用再从1开始看，因为[1,2]和[2,1]是一样的。但对于排列问题，它们不一样，所以如果第一位遍历到2，依然要考虑元素1。因此，排列问题不需要startIdx。

2. 去重

我们每添加新的一位元素，就要从数组第一位开始看，但要跳过已经添加到path中的自己。

代码实现

class Solution(object):
    def backtracking(self, nums, path, result):
        if len(path) == len(nums):
            result.append(path[:])  
            return         

        for i in range(len(nums)):
            if nums[i] in path:
                continue
            path.append(nums[i])
            self.backtracking(nums, path, result)
            path.pop()
        
    def permute(self, nums):
        result, path = [], []
        self.backtracking(nums, path, result)
        return result

47. 全排列Ⅱ

题目链接：47. 全排列 II - 力扣（LeetCode）

思路

谨慎去重

nums包含重复数字，就不能只看当前遍历到的数字在不在path里。只能对自己去重，而不能去重和自己数值相同但序列和自己不同的元素。比如对于[1,1,2]，我们先选1，下一位从[1,1,2]开始选，对于第一个1，是它本身，所以continue，对于第二个1，虽然和已有的1数值相同，但因为位置不同，是要加上去的。

代码实现

class Solution(object):
    def backtracking(self, nums, path, result, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        uset = set()
        for i in range(len(nums)):
            if nums[i] in uset or used[i]:
                continue
            path.append(nums[i])
            uset.add(nums[i])
            used[i] = True
            self.backtracking(nums, path, result, used)
            used[i] =False
            path.pop()

    def permuteUnique(self, nums):
        path, result = [], []
        used = [False] * len(nums)
        self.backtracking(nums, path, result, used)
        return result