回溯篇 – 全排列

全排列问题相比传统组合问题，需要遍历全部数组数据，但同时需要注意顺序，解决办法就是使用used数组。

全排列分为以下两种情况：

• 1 全排列返回数组不需要去重
  • 1 for循环中需要遍历全部数组数据。
  • 2 for循环中需要使用used数组控制跳过已经遍历过的数据。
• 2 全排列返回数组需要去重
  • 1 全排列返回数组不需要去重方法
  • 2 组合总和II去重方法
    • nums 排序
    • if  (i>0 && nums[i-1] == nums[i] && used[i-1] == false)判断

1 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

全排列的重复是树枝内重复。

2 全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

全排列II的重复是树枝内重复和同树层重复。