Open youngyangyang04 opened 3 months ago
private void backtracking(int[] nums, boolean[] used) {
if(path.size() == nums.length){
paths.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++){
if(!used[i]){
used[i] = true;
path.add(nums[i]);
backtracking(nums, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
// 深度1: backtracking([1,2,3], 0), path = [], used = [f,f,f]
i = 0:path = [1],递归 backtracking([1,2,3], 1)。回溯,path = []
i = 1:path = [2],递归 backtracking([1,2,3], 2)。回溯,path = []
i = 2:path = [3],递归 backtracking([1,2,3], 3)。回溯,path = []
// 深度2: 例: backtracking([1,2,3], 1), path = [1], used = [t,f,f]
i = 0:used[0] == true, 继续遍历(去重)
i = 1:path = [1,2],递归 backtracking([1,2,3], 2)。回溯,path = [1]
i = 2:path = [1,3],递归 backtracking([1,2,3], 3)。回溯,path = [1]
// 深度3: 例: backtracking([1,2,3], 2), path = [1,2], used = [t,t,f]
i = 0:used[0] == true, 继续遍历(去重)
i = 1:used[1] == true, 继续遍历(去重)
i = 2:path = [1,2,3],递归 backtracking([1,2,3], 3)。回溯,path = [1,2]
https://www.programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html