leetcode-21-回溯-全排列及其去重
一、[46]全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
- 输入: [1,2,3]
- 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
其中，不需要使用startIndex
used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次
相当于在每个分支上标记使用了那些元素，每个分支，元素只可以使用一次
二、[47]全排列2
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
- 输入：nums = [1,1,2]
- 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
- 输入：nums = [1,2,3]
- 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
1、去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
2、树枝去重（更好理解）
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {continue;
}3、树层去重（效率更高）
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}回溯总结：一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
引自：代码随想录 (programmercarl.com)