Chủ đề · 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

// Naive approach: generate every length-n sequence, then filter — O(n × n!) plus overhead
// Impractical in practice; backtracking is the efficient way
// Demo: permute by swapping positions (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 back
    }
  }

  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 và trường hợp biên.

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.

// Naive approach: generate every length-n sequence, then filter — O(n × n!) plus overhead // Impractical in practice; backtracking is the efficient way // Demo: permute by swapping positions (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 back } } backtrack(0) return result }