回溯：组合、子集、排列 算法总结

一、组合问题

1. 每个元素只能用一次，无同值元素

1. for循环i=index,递归时 backtracking(n, k, i+1, list); //不可重复使用当前元素

2. 每个值只能用一次，用同值元素也不可再用

1. for循环i=index,递归时 backtracking(n, k, i+1, list); //不可重复使用当前元素
2. 用list记录已经用过的元素的值，再遇到时跳过。//之后的重复元素也不可用

3. 每个元素能用多次，无同值元素

for i=startIndex,递归时传 i ，不用+1 //可重复使用当前元素
为防止重复解，需要先排序

4. 每个元素只能用一次，有同值元素

防止重复列表，保证生成列表唯一顺序,先排序。
同时跳过同层使用过的元素if (i != index && candidates[i] == candidates[i - 1]) continue; //有重复元素
for i =startIndex . backtracking时传 i + 1 //不可重复使用当前元素

二、子集问题

1. 所有长度的子集，数组无重复值

在递归函数开头就添加到结果集中。每次变化都需要添加到结果集中。
for i =startIndex + 1, backtracking i + 1 // 不可重复使用当前元素

2. 所有长度的子集，数组有重复值

为防止重复，先排序。
if (i !=startIndex && nums[i] == nums[i - 1])continue; // 只有基础层添加了一次，延伸层不再添加。
在递归函数开头就添加到结果集中。每次变化都需要添加到结果集中。
for i =startIndex + 1, backtracking i + 1 // 不可重复使用当前元素

3. 不可改变顺序，指定长度子集，顺序数组有重复

for i =startIndex + 1, backtracking i + 1 // 不可重复使用当前元素
//同父元素结点下重复使用 某 数，跳过，注意，不同层级则可以重复用
if (set.contains(nums[i])) continue;

三、排列问题

1. 无重复元素数组全排列

全排列。就不用startIndex来切割了，全部排一遍，如果有重复的，跳过即可。
for i = 0 //全排列
if (list.contains(nums[i])) continue; //重复解 则 跳过

2. 有重复元素数组全排列

需要使用 used 数组来判断 相同的之前的 元素 有没有被使用过。如果被使用过就跳过这个元素。
先排序
for i = 0; //全排列
if (i > 0 && nums[i] == nums[i - 1] && used[i-1])continue; // 这个相同的值 在本层已经被使用过了