Pattern · Quay luiTrung bình ~25 phút đọc + làm

Tất Cả Hoán VịPermutations

Hiểu bài

Cho mảng các số nguyên phân biệt nums. Trả về tất cả hoán vị có thể — mỗi phần tử xuất hiện đúng 1 lần trong mỗi hoán vị.

Ví dụ:

nums = [1, 2, 3]
output = [
  [1,2,3], [1,3,2],
  [2,1,3], [2,3,1],
  [3,1,2], [3,2,1]
]
// n! = 3! = 6 hoán vị

nums = [0, 1]
output = [[0,1], [1,0]]

Khác subsets: mỗi phần tử được dùng đúng 1 lần và thứ tự quan trọng (permutation khác combination).

Dùng mảng used để theo dõi phần tử đã dùng trong hoán vị hiện tại.

Cách cơ bảnO(n × n!) time — n! hoán vị, mỗi cái tốn O(n) để copy

// Cách ngây thơ: sinh mọi chuỗi độ dài n rồi lọc — O(n × n!) thêm overhead
// Thực tế không khả thi; backtracking chính là cách hiệu quả nhất
// Demo: hoán vị bằng cách hoán đổi vị trí (in-place swap)
function permuteSwap(nums: number[]): number[][] {
  const result: number[][] = []

  function backtrack(start: number) {
    if (start === nums.length) {
      result.push([...nums])
      return
    }
    for (let i = start; i < nums.length; i++) {
      ;[nums[start], nums[i]] = [nums[i], nums[start]]  // swap
      backtrack(start + 1)
      ;[nums[start], nums[i]] = [nums[i], nums[start]]  // swap lại
    }
  }

  backtrack(0)
  return result
}

Vì sao cách này chậm:

Phiên bản swap cũng đạt O(n×n!) nhưng sửa mảng gốc (in-place).

Phiên bản dùng mảng used tách biệt hơn, không sửa input — phù hợp hơn khi đề cấm sửa input.

Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan

Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.

Mở khoá Pro Xem Lifetime

Hiểu bài

Cho mảng các số nguyên phân biệt nums. Trả về tất cả hoán vị có thể — mỗi phần tử xuất hiện đúng 1 lần trong mỗi hoán vị.

Ví dụ:

nums = [1, 2, 3]
output = [
  [1,2,3], [1,3,2],
  [2,1,3], [2,3,1],
  [3,1,2], [3,2,1]
]
// n! = 3! = 6 hoán vị

nums = [0, 1]
output = [[0,1], [1,0]]

Khác subsets: mỗi phần tử được dùng đúng 1 lần và thứ tự quan trọng (permutation khác combination).

Dùng mảng used để theo dõi phần tử đã dùng trong hoán vị hiện tại.

// Cách ngây thơ: sinh mọi chuỗi độ dài n rồi lọc — O(n × n!) thêm overhead // Thực tế không khả thi; backtracking chính là cách hiệu quả nhất // Demo: hoán vị bằng cách hoán đổi vị trí (in-place swap) function permuteSwap(nums: number[]): number[][] { const result: number[][] = [] function backtrack(start: number) { if (start === nums.length) { result.push([...nums]) return } for (let i = start; i < nums.length; i++) { ;[nums[start], nums[i]] = [nums[i], nums[start]] // swap backtrack(start + 1) ;[nums[start], nums[i]] = [nums[i], nums[start]] // swap lại } } backtrack(0) return result }