Open youngyangyang04 opened 3 months ago
private void backtracking(int[] nums, int start) {
paths.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
// 深度1: backtracking([1,2,2], 0), path = []
i = 0:path = [1],递归 backtracking([1,2,3], 1),加入 paths。回溯,path = []
i = 1:path = [2],递归 backtracking([1,2,3], 2),加入 paths。回溯,path = []
i = 2:满足 nums[i] == nums[i - 1], 继续遍历(去重)
// 深度2: 例: backtracking([1,2,2], 1), path = [1]
i = 1:path = [1,2],递归 backtracking([1,2,3], 2),加入 paths。回溯,path = [1]
i = 2:满足 nums[i] == nums[i - 1], 继续遍历(去重)
// 深度3: 例: backtracking([1,2,2], 2), path = [1,2]
i = 2:path = [1,2,2],递归 backtracking([1,2,3], 3),加入 paths。回溯,path = [1,2]
没必要用used进行记录。
class Solution:
def subsetsWithDup(self, nums):
result = []
path = []
nums.sort()
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
result.append(path[:]) # 收集子集
for i in range(startIndex, len(nums)):
# used[i - 1] == True,说明同一树枝 nums[i - 1] 使用过
# used[i - 1] == False,说明同一树层 nums[i - 1] 使用过
# 而我们要对同一树层使用过的元素进行跳过
if i > startIndex and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
https://www.programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html