Bài 46 Leetcode: Permutations

Đề bài:

Cho một mảng nums gồm các số nguyên phân biệt, trả về tất cả các hoán vị có thể. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ 1:

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

Ví dụ 2:

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

Ví dụ 3:

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

Ràng buộc:

  • 1 <= độ dài của nums <= 6
  • -10 <= nums[i] <= 10
  • Tất cả các số nguyên trong nums đều là duy nhất.

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

class Solution {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;

    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;
      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ị của một mảng `nums`. 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. Gọi hàm `dfs` để thực hiện tìm kiếm theo đệ quy và tạo ra các hoán vị.

3. 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.

4. 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.

– Đá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ị của mảng `nums` được lưu trong vector 2 chiều `ans`.

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

class Solution {
  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();

    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;
      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 permute(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
        used[i] = True
        path.append(num)
        dfs(path)
        path.pop()
        used[i] = False

    dfs([])
    return ans

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.