# 46. Permutations & 47. Permutations II

[**46. Permutations**](https://leetcode.com/problems/permutations/description/)

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]
]
```

**My Solutions:**

和combinations类似，temp的长度和nums长度相等的时候把temp加入结果并直接返回。区别有

* 注意dfs的for loop中i=0，因为是permutation（置换），所以所有排列方式都要包含到
* 注意if (!temp.contains(nums\[i]))，确保不会有重复数字

```java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, nums, new ArrayList<Integer>(), 0);
        return res;
    }

    private void backtrack(List<List<Integer>> res, int[] nums, List<Integer> temp, int start) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (temp.contains(nums[i])) continue;
            temp.add(nums[i]);
            backtrack(res, nums, temp, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}
```

还可以用一个boolean\[] 检查数字是不是已经被用过了。这个模版可以套用在#47题。

```java
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(res, nums, new ArrayList<Integer>(), 0, used);
    return res;
}

private void backtrack(List<List<Integer>> res, int[] nums, List<Integer> temp, int depth, boolean[] used) {
    if (temp.size() == nums.length) {
        res.add(new ArrayList<Integer>(temp));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        temp.add(nums[i]);
        used[i] = true;
        backtrack(res, nums, temp, i + 1, used);
        temp.remove(temp.size() - 1);
        used[i] = false; // 回来的时候取消掉，因为可以在temp里这个元素已经去掉，可以再次使用
    }
}
```

[ **47. Permutations II**](https://leetcode.com/problems/permutations-ii/description/)

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]
]
```

**My Solutions：**

和上题类似，但要多加两个限定条件：

1。 去掉duplicates，和combination sum II 类似，需要先排序，检查现在的元素和下一个元素是否不同。

2。 必须加一个used array，确保一个index只被用一次 （因为上题全部是不同数字，所以可以用 if (!temp.contains(nums\[i]))）

```java
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums); // 必须要sort
        
        backtrack(list, new ArrayList<Integer>(), nums, new boolean[nums.length]);
        return list;
    }
    
    public void backtrack(List<List<Integer>> list, List<Integer> temp, int[] nums, boolean[] used) {
        
        if (temp.size() == nums.length) {
            list.add(new ArrayList<Integer>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && used[i - 1]) continue; // 新步骤
            temp.add(nums[i]);
            used[i] = true;
            backtrack(res, nums, temp, i + 1, used);
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
}
```

[**1079. Letter Tile Possibilities**](https://leetcode.com/problems/letter-tile-possibilities/)

You have `n`  `tiles`, where each tile has one letter `tiles[i]` printed on it.

Return *the number of possible non-empty sequences of letters* you can make using the letters printed on those `tiles`.

**Example 1:**

<pre><code><strong>Input: tiles = "AAB"
</strong><strong>Output: 8
</strong><strong>Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: tiles = "AAABBC"
</strong><strong>Output: 188
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: tiles = "V"
</strong><strong>Output: 1
</strong></code></pre>

**My Solutions：**

和上题以及subset类似。

1。用Set\<String> 去重，所以不需要sort。

2。需要一个used array，确保一个index只被用一次 。

```java
class Solution {
    public int numTilePossibilities(String tiles) {
        Set<String> set = new HashSet<>();
        boolean[] used = new boolean[tiles.length()];
        backtrack(tiles, "", used, set);
        return set.size() - 1;
    }

    private void backtrack(String tiles, String temp, boolean[] used, Set<String> set) {
        set.add(temp);
        for (int i = 0; i < tiles.length(); i++) {
            if (used[i]) continue;
            used[i] = true;
            backtrack(tiles, temp + tiles.charAt(i), used, set);
            used[i] = false;
        }
    }
}
```