算法练习Day23 （Leetcode/Python-回溯算法）

46. Permutations

Given an array?nums?of distinct integers, return?all the possible permutations. You can return the answer in?any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


思路：此题可用回溯法做排列问题。待取元素的candiate内无重复，区别于之前的组合问题，这里在横向遍历时for循环需要遍历所有元素，而不是在startIndex之后的元素（因为排列可以取[1,2,3],[1,3,2]这样的元素，组合的话就只能取[1,2,3]，而无[1,3,2]）。但是为了避免与纵向已经取过的元素在一个path里重复，要设置一个used元素记录之前path里已经取过的元素。这个used元素也需要在回溯中调整。

class Solution(object):
    def backtrack(self, nums, path, result, used):
        if len(path) == len(nums):
            result.append(path[:]) # 记得用[:]
            return 
        for i in range(len(nums)): # use used to remove duplicated item
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtrack(nums, path, result, used)
            path.pop()
            used[i] = False

    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        used = len(nums) * [False]
        self.backtrack(nums, [], result, used)
        return result

491. Non-decreasing Subsequences

Given an integer array?nums, return?all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in?any order.

Example 1:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

思路：找出一个数组中的所有升序子序列，注意这个子序列不需要在原数组中连续。用递归写出暴力解法的思路枚举出所有可能的子序列就可以了。第i+1层横向遍历从startIndex = i+1开始。

关键点在于去重。其实只要每次横向遍历不用本次横向遍历里已经用过的元素就可以了。因为这个新元素最后可以取得的有效升序子序列之能是之前这个元素可以取得的有效子集。因为有效升序子集不需要连续！！

class Solution(object):
    def backtrack(self, nums, startIndex, path, result):
        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:  #[2,7,8,4,7,9]  比如这种情况下，第二个7就不能再被取，因为第二个7能组合出来的有效升序子序列一定能被第一个7组合出来。
                continue
            uset.add(nums[i])
            path.append(nums[i])
            self.backtrack(nums, i +1, path, result)
            path.pop()


    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        path = []
        self.backtrack(nums, 0, path, result)
        return result