回溯算法

90. Subsets IIGiven an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: 12Input: nums = [1,2,2]Output: [[],[1],[1,2],[1,2,2],[2],[2,2]] Example 2: 12Input: nums = [0]Output: [[],[0]] 题目大意给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（即幂集）。幂集需包含所有可能的子集（包括空集和数组本身），且不能有重复子集，结果顺序可任意。 例如： 输入 nums = [1,2,2]，输出 [[],[1],[1,2],[1,2,2],[2],[2,2]]（共 6 个子集，无重复）； 输入 nums...

46. PermutationsGiven an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1: 12Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: 12Input: nums = [0,1]Output: [[0,1],[1,0]] Example 3: 12Input: nums = [1]Output: [[1]] 题目大意给定一个无重复元素的整数数组 nums，返回该数组所有可能的全排列。全排列是指包含数组所有元素的有序序列，且每个元素仅出现一次，结果顺序可任意。 例如： 输入 nums = [1,2,3]，输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]（共 3! = 6...

491. Non-decreasing SubsequencesGiven 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: 12Input: 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]] Example 2: 12Input: nums = [4,4,3,2,1]Output: [[4,4]] 题目大意给定一个整数数组 nums，返回所有不同的、长度至少为 2 的非递减子序列。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。 例如： 输入 nums = [4,6,7,7]，输出包含...

78. SubsetsGiven an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: 12Input: nums = [1,2,3]Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: 12Input: nums = [0]Output: [[],[0]] 题目大意给定一个无重复元素的整数数组 nums，返回该数组所有可能的子集（即幂集）。幂集需包含所有可能的子集（包括空集和数组本身），且不能有重复子集，结果顺序可任意。 例如： 输入 nums = [1,2,3]，输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]（共 2³=8...

93. Restore IP AddressesA valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots...

131. Palindrome PartitioningGiven a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example 1: 12Input: s = "aab"Output: [["a","a","b"],["aa","b"]] Example 2: 12Input: s = "a"Output: [["a"]] 题目大意给定一个字符串 s，将其分割成若干个子串，使得每个子串都是回文串。返回所有可能的分割方案。 例如： 输入 s = "aab"，输出...

40. Combination Sum IIGiven a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations. Example 1: 12345678Input: candidates = [10,1,2,7,6,1,5], target = 8Output: [[1,1,6],[1,2,5],[1,7],[2,6]] Example 2: 123456Input: candidates = [2,5,2,1,2], target =...

216. Combination Sum IIIFind all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order. Example 1: 12345Input: k = 3, n = 7Output: [[1,2,4]]Explanation:1 + 2 + 4 = 7There are no other valid combinations. Example 2: 1234567Input: k...

77. CombinationsGiven two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order. Example 1: 1234Input: n = 4, k = 2Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Explanation: There are 4 choose 2 = 6 total combinations.Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination. Example 2: 123Input: n = 1, k = 1Output: [[1]]Explanation: There is 1 choose 1 = 1 total...