Bài 47 Leetcode: Permutations II

Đề bài:

Cho một tập hợp số nums có thể chứa các phần tử trùng nhau, trả về tất cả các hoán vị duy nhất có thể có, theo bất kỳ thứ tự nào.

Ví dụ 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Ví dụ 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Ràng buộc:

• 1 <= độ dài của nums <= 8
• -10 <= nums[i] <= 10

Giải thích thuật toán bằng C ++

class Solution {
 public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> ans;
    ranges::sort(nums);
    dfs(nums, vector<bool>(nums.size()), {}, ans);
    return ans;
  }

 private:
  void dfs(const vector<int>& nums, vector<bool>&& used, vector<int>&& path,
           vector<vector<int>>& ans) {
    if (path.size() == nums.size()) {
      ans.push_back(path);
      return;
    }

    for (int i = 0; i < nums.size(); ++i) {
      if (used[i])
        continue;
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
        continue;
      used[i] = true;
      path.push_back(nums[i]);
      dfs(nums, move(used), move(path), ans);
      path.pop_back();
      used[i] = false;
    }
  }
};

Đây là một giải thuật để tạo ra tất cả các hoán vị duy nhất của một mảng `nums`, bao gồm cả các phần tử trùng nhau. Dưới đây là giải thích chi tiết về giải thuật:

1. Khởi tạo một vector 2 chiều `ans` để lưu trữ tất cả các hoán vị.

2. Sắp xếp lại mảng `nums` để đảm bảo các phần tử trùng nhau nằm cạnh nhau.

3. Gọi hàm `dfs` để thực hiện tìm kiếm theo đệ quy và tạo ra các hoán vị.

4. Trong hàm `dfs`, kiểm tra nếu kích thước của `path` (đã chọn các số) bằng kích thước của `nums` (số lượng các số trong mảng). Điều này đại diện cho việc đã tạo thành một hoán vị và ta thêm `path` vào `ans` và kết thúc đệ quy.

5. Vòng lặp qua các vị trí `i` từ 0 đến `nums.size() – 1`:

– Kiểm tra nếu `used[i]` (đã sử dụng số tại vị trí `i`) là `true`, tức là đã sử dụng số này trong một hoán vị trước đó, ta bỏ qua vòng lặp.

– Kiểm tra nếu `i` lớn hơn 0 và số tại vị trí `i` trong `nums` bằng số tại vị trí `i – 1` trong `nums` và số tại vị trí `i – 1` chưa được sử dụng (`!used[i – 1]`), tức là sẽ tạo ra các hoán vị trùng lặp. Ta bỏ qua vòng lặp để tránh tạo ra các hoán vị trùng lặp.

– Đánh dấu `used[i]` là `true` để chỉ ra số tại vị trí `i` đã được sử dụng.

– Thêm số tại vị trí `i` vào `path`.

– Gọi đệ quy hàm `dfs` với các tham số đã được cập nhật.

– Xóa số cuối cùng trong `path` (để thử các số khác).

– Đánh dấu `used[i]` là `false` để đánh dấu số tại vị trí `i` có thể được sử dụng trong các hoán vị tiếp theo.

Kết quả là tất cả các hoán vị duy nhất của mảng `nums` được lưu trong vector 2 chiều `ans`. Các hoán vị được tạo ra theo bất kỳ thứ tự nào.

Giải thích thuật toán bằng Java

class Solution {
  public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);
    dfs(nums, new boolean[nums.length], new ArrayList<>(), ans);
    return ans;
  }

  private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
    if (path.size() == nums.length) {
      ans.add(new ArrayList<>(path));
      return;
    }

    for (int i = 0; i < nums.length; ++i) {
      if (used[i])
        continue;
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
        continue;
      used[i] = true;
      path.add(nums[i]);
      dfs(nums, used, path, ans);
      path.remove(path.size() - 1);
      used[i] = false;
    }
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    ans = []
    used = [False] * len(nums)

    def dfs(path: List[int]) -> None:
      if len(path) == len(nums):
        ans.append(path.copy())
        return

      for i, num in enumerate(nums):
        if used[i]:
          continue
        if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
          continue
        used[i] = True
        path.append(num)
        dfs(path)
        path.pop()
        used[i] = False

    nums.sort()
    dfs([])
    return ans