回溯算法思想解决排列，子集，组合问题汇总

回溯算法思想解决排列，组合/子集的九种(3x3)类型。

类型一：元素不重复，不可复选。

类型二：元素可重复，不可复选。

类型三：元素无重复，可复选。

注：
1.涉及到回溯算法, 多画递归树去思考如何遍历和剪枝。

2.组合实际是在子集的基础上增加了条件。

3.排列不受序列顺序控制，组合/子集受序列顺序控制。

剪枝技巧说明：

类型一：

1.组合/子集, 使用start参数控制树的高度，避免重复的子集。

2.排列，使用used数组表示选择列表, used[i] == 1表示元素已被选择, 反之元素未被选择, 可剪枝。

类型二：

1.组合/子集, 需剪去相同元素带来的相同子集分支，因此需要先对目标数组排序，使用start参数控制树的高度，避免重复的子集，然后当满足i > 0 && nums[i] == nums[i - 1]条件时, 剪枝。

假设存在[1, 2, 2’], 其中2和2’是同一个元素，为了区分，加'进行区分。所以满足i > 0 && nums[i] == nums[i - 1]条件剪的枝对应[1, 2’]。即如果某节点存在值相同的相邻树枝, 保留遍历第一条, 其余剪枝。

2.排列, 标准下的排列会产生重复的组合是因为我们把排列相同元素形成的不同排列序列当做了不同的排列组合，所以关键点在于相同元素的不同排列序列,因此为了解决类型二下的排列问题，我们不仅需要满足i > 0 && nums[i] == nums[i - 1]这个条件, 还需要固定元素的相对位置。

假设存在[1, 2, 2’, 2’’], 其中要满足 2在2’之前被选择, 2’ 在 2’’之前被选择。因此新的剪枝条件变成i > 0 && nums[i] == nums[i - 1] && !nums[i - 1]。

类型三：

1.组合/子集, 在前两种类型中，我们使用start变量控制树的高度，避免重复的子集，每次递归时start是加1的。为了满足元素可被多次复选，在向下递归时, 将start + 1 改为 start，相当于为子分支增加一条树枝, 该树枝的值源于父节点，这样就可以无限复用已经选择的元素了。但要注意跳出条件。

2.排列, 在前两种类型中，我们使用used数组表示选择列表，控制可选的元素节点。因此为了实现元素可复选，只需去掉used数组剪枝即可。