46. Permutations & 47. Permutations II

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

My Solutions:

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

• 注意dfs的for loop中i=0，因为是permutation（置换），所以所有排列方式都要包含到

• 注意if (!temp.contains(nums[i]))，确保不会有重复数字

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题。

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

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]))）

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

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:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

My Solutions：

和上题以及subset类似。

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

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

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;
        }
    }
}