# 46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

```Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]```

## 解法：

```    List<List<Integer>> res = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0) return res;
LinkedList<Integer> p = new LinkedList<>();
used = new boolean[nums.length];
permuteHelper(nums,0,p);
return res;
}

public void permuteHelper(int[] nums,int index,LinkedList<Integer> list){
if (nums.length == index) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
res.add(listClone);
return;
}

for (int i = 0 ;i< nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,index+1,list);
used[i] = false;
list.removeLast();
}
}
}```

```    public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permuteRes = new ArrayList<>();
boolean[] used = new boolean[nums.length];
if (nums == null || nums.length == 0) return permuteRes;
LinkedList<Integer> p = new LinkedList<>();
permuteHelper(nums,p,permuteRes,used);
return permuteRes;
}

public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
permuteRes.add(listClone);
return;
}
for (int i = 0 ;i<nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,permuteRes,used);
used[i] = false;
list.removeLast();
}
}
}```

```    List<List<Integer>> res = new ArrayList<>();
boolean[] used;   //采用的是全局变量，记录当前的元素是否已经使用了
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];  // 注意，虽然 used是定义的类的成员变量，但是分配空间可以在子函数里面进行
if (nums.length == 0||nums == null) return res;   //如果数组为空或者数组里面没有元素 返回res
LinkedList<Integer> p = new LinkedList<>();  //这里定义为LinkedList的目的是在结尾进行增删操作。
// 如果是ArrayList的话，只能在结尾添加，不能在结尾删除
permute_recursion( nums,0,p);   // 初始时候。index的值为0,
return res;
}

/**
*
* @param nums
* @param index
* @param list
*/
public void permute_recursion(int[] nums, int index, LinkedList<Integer> list ) {
if (nums.length == index) {    //当前的索引已经超出了 数组的最大的索引 ，说明list中存储的数据已经是一个完整的组合了
LinkedList<Integer> list_clone = (LinkedList<Integer>)list.clone();//java参数是引用专递机制，发现list中存储的是一个完整的组合后，
//将这个组合  克隆一份  添加到res中，否则后续的程序会修改list
res.add(list_clone);  //将克隆后的组合添加到res中
return;
}

for (int i =0;i <nums.length ;i++){
if (used[i] == false ){   //这里采用的是一个boolean的数组，来记录当前的索引的元素是否已经使用过
list.addLast(nums[i]); //将新的元素添加到list的尾部，
used[i]  = true;  // 同时将used的数组 设置为true  表示这个元素已经使用过了
permute_recursion(nums,index+1,list);  // 递归
used[i] = false; //清除这个used的标记
list.removeLast(); // 递归完毕后，将最后一个数据删除，以便于尝试其他的组合，这一步也就是回溯算法的“回溯”的体现所在
}
}
}```

# 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

```Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]```

## 解法一：

``` public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permuteRes = new ArrayList<>();
Set<LinkedList<Integer>> set = new HashSet<>();
boolean[] used = new boolean[nums.length];;
if (nums == null || nums.length == 0) return permuteRes;
LinkedList<Integer> p = new LinkedList<>();
permuteHelper(nums,p,set,used);
return new ArrayList<>(set);
}

public void permuteHelper(int[] nums,LinkedList<Integer> list, Set<LinkedList<Integer>> set, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
set.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,set,used);
used[i] = false;
list.removeLast();
}
}
}```

## 解法二：

```    public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> permuteRes = new ArrayList<>();
boolean[] used = new boolean[nums.length];
if (nums == null || nums.length == 0) return permuteRes;
permuteHelper(nums,new LinkedList<>(),permuteRes,used);
return permuteRes;
}

public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
permuteRes.add(listClone);
return;
}

for (int i = 0 ;i< nums.length;i++){
if(used[i]||(i>0&&nums[i] == nums[i-1]&&used[i-1]==false))  continue;
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,permuteRes,used);
used[i] = false;
list.removeLast();
}
}
```

## 总结：

0 条评论

• ### LeetCode <dfs>108&109. Array & List to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

• ### LeetCode <dp>152&628 Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (conta...

• ### Mysql基础

1、Serializable （串行化）：最严格的级别，事务串行执行，资源消耗最大；

• ### LeetCode91|寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个...

• ### LeetCode_1. Two Sum_Solution

这道题目的意思是给定一个数组和一个值，要求出这个数组中两个值的和等于这个给定值target。

• ### 普通程序员该如何进阶为全栈工程师？

如何成为一名全栈工程师（full stack developer)？互联网最热的话题之一。LinkedIn, Facebook上标榜自己是全栈工程师的人也越来...

• ### 顺序栈的实现和两栈共享空间

顺序栈的实现和两栈共享空间 一.顺序栈的实现        栈(stack)是限定仅在表尾进行插入或删除操作的线性表。我们把允许插入和删除的一端称为栈顶(t...

• ### Android ListView异步加载图片乱序问题，原因分析及解决方案

在Android所有系统自带的控件当中，ListView这个控件算是用法比较复杂的了，关键是用法复杂也就算了，它还经常会出现一些稀奇古怪的问题，让人非常头疼。比...