Open youngyangyang04 opened 3 months ago
我爱你Carl,谢谢你无偿分享好知识
private void backtracking(int[] nums, int start) {
if(path.size() >= 2){
paths.add(new ArrayList<>(path));
}
Set<Integer> set = new HashSet<>();
for(int i = start; i < nums.length; i++){
if(!path.isEmpty() && nums[i] < path.get(path.size() - 1)){
continue; // 保证递增
}
if(set.contains(nums[i])) continue; // 去重
set.add(nums[i]);
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
// 深度1: backtracking([4,7,6,7], 0), path = []
i = 0:path = [4],递归 backtracking([4,6,7,7], 1)。回溯,path = []
i = 1:path = [7],递归 backtracking([4,6,7,7], 2)。回溯,path = []
i = 2:path = [6],递归 backtracking([4,6,7,7], 3)。回溯,path = []
i = 3:满足 set.contains(7),继续遍历(去重)
// 深度2: 例: backtracking([4,7,6,7], 1), path = [4]
i = 1:path = [4,7],递归 backtracking([4,6,7,7], 2),加入 paths。回溯,path = [4]
i = 2:path = [4,6],递归 backtracking([4,6,7,7], 3),加入 paths。回溯,path = [4]
i = 3:满足 set.contains(7),继续遍历(去重)
// 深度3: 例: backtracking([4,7,6,7], 2), path = [4,7]
i = 2:满足 6 < 7,继续遍历(保证递增)
i = 3:path = [4,7,7],递归 backtracking([4,6,7,7], 4),加入 paths。回溯,path = [4,7]
https://www.programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html