LeetCode Day 29 Backtracking Algorithm (5/6)
Published:
Two days left of backtracking algorithm!
Question 1
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.
This question is a bit like LC 90, but this question does not allow you to sort before finding the subset, otherwise it will affect the resulting subset.
class Solution:
def findSubsequences(self, nums):
result = []
path = []
self.backtracking(nums, 0, path, result)
return result
def backtracking(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:
continue
uset.add(nums[i])
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
Question 2
Given an array
numsof distinct integers, return all the possible permutations. You can return the answer in any order.
Because combinations are ordered, e.g., [1,2] and [2,1] are two sets, you can’t use the original startindex to control the deletion of duplicates; instead, you can use an used to identify which elements are duplicates.
class Solution:
def permute(self, nums):
result = []
self.backtracking(nums, [], [False] * len(nums), result)
return result
def backtracking(self, 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])
self.backtracking(nums, path, used, result)
path.pop()
used[i] = False
Question 3
Given a collection of numbers,
nums, that might contain duplicates, return all possible unique permutations in any order.
The question was changed to one where the nums contain duplicate elements, but the result of the arrangement cannot have duplicates, which again involves pruning operations.
class Solution:
def permuteUnique(self, nums):
nums.sort()
result = []
self.backtracking(nums, [], [False] * len(nums), result)
return result
def backtracking(self, 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]:
continue
used[i] = True
path.append(nums[i])
self.backtracking(nums, path, used, result)
path.pop()
used[i] = False