Permutations: xây dựng mọi thứ tự bằng backtracking

Lần đầu tôi viết bộ sinh hoán vị, tôi dùng itertools.permutations của Python rồi chuyển sang bài tiếp theo. Bốn dòng, output đúng, xong. Tuần sau tôi gặp một biến thể cần prune cây tìm kiếm ngay giữa recursion, và lúc đó thư viện không giúp được gì. Đó là lý do thực sự để hiểu bản backtracking: không phải vì itertools sai, mà vì nó là một hộp đen vỡ ngay khi bài toán thay đổi hình dạng.

LeetCode 46 hỏi: cho một mảng các số nguyên phân biệt, trả về tất cả các hoán vị có thể. Với [1, 2, 3], đáp án là sáu thứ tự: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].

Các constraint thực sự ràng buộc điều gì

1 <= nums.length <= 6. Sáu phần tử tối đa. Số hoán vị của n phần tử phân biệt là n!, nên ở n=6 đó là 720 hoán vị. Mọi cách tiếp cận có thể nghĩ đến — kể cả naive nhất — đều chạy thoải mái trong giới hạn thời gian.

-10 <= nums[i] <= 10, tất cả phân biệt. Constraint "phân biệt" làm nhiều việc nhất: bạn không bao giờ cần xử lý logic loại trùng lặp. Mỗi phần tử có thể nhận dạng duy nhất qua chỉ số. Nếu có phần tử trùng, bạn sẽ đang làm LeetCode 47, bài khó hơn trong series này. Ở đây bạn có thể index phần tử theo vị trí mà không lo hai giá trị bằng nhau.

Hai constraint này cùng cho phép bạn dùng bất kỳ algorithm đúng nào. Câu hỏi không phải "làm sao cho đủ nhanh?" mà là "version nào dạy được pattern có thể tổng quát hoá?"

Tại sao gọi thư viện là nước đi sai đầu tiên

Python làm rất dễ:

from itertools import permutations
 
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        return [list(p) for p in permutations(nums)]

C# không có tương đương trực tiếp — Enumerable không có method sinh hoán vị — nên dù sao cũng phải implement thủ công. Nhưng kể cả trong Python, bắt đầu từ đây là phản tác dụng: itertools.permutations không cho bạn trực giác gì về cấu trúc của quá trình liệt kê. Bạn không thể prune nó, không thể thay đổi quy tắc sắp xếp, và không thể giải thích nó trong phỏng vấn. Output đúng; hiểu biết vắng mặt.

Time: O(n! _ n) — n! hoán vị, mỗi cái cần O(n) để copy vào list kết quả. Space: O(n! _ n) cho output, cộng O(n) cho trạng thái iterator nội bộ. Cùng chi phí asymptotic với các cách tiếp cận tường minh.

Tôi đưa vào đây vì nó là cách tiếp cận thực sự và source bài gốc có đề cập, nhưng tôi sẽ không dùng nó nếu có thể cần sửa logic.

Backtracking: xây cây quyết định một cách tường minh

Ý tưởng cốt lõi là nghĩ mỗi hoán vị như một chuỗi lựa chọn: chọn phần tử đầu tiên, rồi chọn phần tử thứ hai từ số còn lại, rồi phần tử thứ ba từ phần còn lại, v.v. Cấu trúc là một cây trong đó mỗi level tương ứng với một vị trí trong hoán vị.

Mỗi đường đi từ gốc đến lá là một hoán vị hoàn chỉnh. Algorithm đi qua cây này theo thứ tự DFS, xây dựng đường đi khi đi xuống và xoá nó khi quay lui.

Để tránh chọn cùng một phần tử hai lần, bạn cần theo dõi phần tử nào đang có trong đường đi hiện tại. Cách gọn nhất là dùng mảng boolean used được đánh index theo vị trí. Tại mỗi lần gọi đệ quy, duyệt qua tất cả vị trí; bỏ qua bất kỳ vị trí nào đã được đánh dấu. Khi bạn thêm phần tử ở index i, set used[i] = True trước khi gọi đệ quy và used[i] = False sau — đó là bước "undo" làm cho backtracking hoạt động.

Một biến thể khéo hơn của cách này bỏ qua mảng used và kiểm tra if num in current_permutation thay thế. Cách đó đúng nhưng tốn O(n) mỗi lần kiểm tra thay vì O(1), nên về mặt hằng số nó chậm hơn. Với n <= 6 bạn sẽ không bao giờ nhận ra sự khác biệt, nhưng thói quen dùng used array chuyển giao tốt hơn sang input lớn hơn.

Trace từng bước với [1, 2, 3]

gọi backtrack(), current=[], used=[F,F,F]
  thử i=0 (val=1): current=[1], used=[T,F,F]
    thử i=1 (val=2): current=[1,2], used=[T,T,F]
      thử i=2 (val=3): current=[1,2,3], used=[T,T,T]
        len == 3 → thêm [1,2,3] vào result; return
      undo i=2: current=[1,2], used=[T,T,F]
    undo i=1: current=[1], used=[T,F,F]
    thử i=2 (val=3): current=[1,3], used=[T,F,T]
      thử i=1 (val=2): current=[1,3,2], used=[T,T,T]
        len == 3 → thêm [1,3,2] vào result; return
      undo i=1: current=[1,3], used=[T,F,T]
    undo i=2: current=[1], used=[T,F,F]
  undo i=0: current=[], used=[F,F,F]
  ... (lặp lại cho i=1, i=2 làm lựa chọn đầu tiên)

Bước undo là toàn bộ cơ chế. Thiếu nó, mảng used tích luỹ các dấu và các lần gọi sau sẽ thấy trạng thái bị nhiễm vĩnh viễn.

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        n = len(nums)
        used = [False] * n
        current = []
 
        def backtrack():
            if len(current) == n:
                result.append(current[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                current.append(nums[i])
                backtrack()
                current.pop()
                used[i] = False
 
        backtrack()
        return result

Bản copy current[:] ở base case không phải tùy chọn. current là một list duy nhất bị recursion thay đổi suốt — nếu bạn append chính đối tượng list đó, mọi entry trong result đều trỏ về cùng một list, list đó sẽ rỗng khi recursion kết thúc. Copy khi thu thập.

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var result = new List<IList<int>>();
        var current = new List<int>();
        var used = new bool[nums.Length];
 
        void Backtrack() {
            if (current.Count == nums.Length) {
                result.Add(new List<int>(current));
                return;
            }
            for (int i = 0; i < nums.Length; i++) {
                if (used[i]) continue;
                used[i] = true;
                current.Add(nums[i]);
                Backtrack();
                current.RemoveAt(current.Count - 1);
                used[i] = false;
            }
        }
 
        Backtrack();
        return result;
    }
}

Time: O(n! _ n). Số lá trong cây quyết định là n!, và ghi mỗi lá vào result tốn O(n). Space: O(n! _ n) cho output cộng O(n) cho độ sâu call stack, mảng used, và current.

Swap-based backtracking: không cần mảng phụ

Có một version chặt hơn tránh được cả mảng used lẫn list current bằng cách thao tác trực tiếp trên nums. Ý tưởng: ở mỗi level đệ quy, các phần tử bên trái chỉ số start đã được đặt vào vị trí. Để chọn phần tử tiếp theo, swap từng phần tử còn lại vào vị trí start, gọi đệ quy, rồi swap lại.

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
 
        def backtrack(start: int):
            if start == len(nums):
                result.append(nums[:])
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]
 
        backtrack(0)
        return result

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var result = new List<IList<int>>();
 
        void Backtrack(int start) {
            if (start == nums.Length) {
                result.Add(new List<int>(nums));
                return;
            }
            for (int i = start; i < nums.Length; i++) {
                (nums[start], nums[i]) = (nums[i], nums[start]);
                Backtrack(start + 1);
                (nums[start], nums[i]) = (nums[i], nums[start]);
            }
        }
 
        Backtrack(0);
        return result;
    }
}

Khi start == 0 và i == 0, swap là no-op (đổi chỗ phần tử với chính nó), nên [1, 2, 3] vẫn là [1, 2, 3] — hoán vị đầu tiên là thứ tự gốc của mảng. Khi start == 0 và i == 1, bạn được [2, 1, 3], rồi đệ quy để fix các vị trí 1 và 2 với 2 đã được đặt sẵn. Thao tác swap lại sau lần gọi đệ quy phục hồi nums về đúng trạng thái trước iteration đó, đó là điều làm cho vòng lặp đúng.

Version này không dùng cấu trúc phụ nào ngoài call stack và output list. Về big-O nó giống nhau: O(n! _ n) time, O(n! _ n + n) space. Hằng số thực tế hơi tốt hơn vì không có bước scan mảng used và không có list current cần duy trì.

Đánh đổi là khả năng đọc hiểu. Version dùng used array làm tường minh logic "chọn từ số còn lại" và dễ verify hơn. Version swap compact nhưng invariant ("các phần tử bên trái start đã được đặt") nằm ẩn trong trạng thái mảng, khiến nó khó debug hơn và khó thích nghi hơn khi cần thêm điều kiện prune.

Các edge case

Một phần tử, nums = [1]: base case kích hoạt ngay lần gọi đầu tiên (len(current) == 1 == n), và [[1]] được trả về. Cả ba cách đều xử lý trường hợp này mà không cần special-case.

Hai phần tử, nums = [0, 1]: cho ra [[0,1],[1,0]]. Đáng kiểm tra vì version swap ghé qua i == start ở iteration đầu tiên (swap no-op), đệ quy, rồi thử i == start+1 (swap thực). Cả hai thứ tự đều được sinh ra.

Giá trị âm: không có code path nào rẽ nhánh dựa trên giá trị phần tử, nên nums = [-1, 0, 1] hoạt động giống hệt [1, 2, 3]. Range -10 <= nums[i] <= 10 không liên quan đến algorithm.

Tất cả phần tử được bài toán đảm bảo phân biệt — cách tiếp cận dùng used array dựa vào điều này. Nếu bạn đưa vào phần tử trùng lặp, output sẽ chứa các hoán vị trùng nhau (LeetCode 47 thêm bước sort + skip để xử lý đó). Version swap cũng gặp vấn đề tương tự.

So sánh

Cả ba đều là O(n! * n) — đây là lower bound lý thuyết thông tin cho việc sinh tất cả hoán vị. Bạn không thể làm tốt hơn; có n! output mỗi cái dài n.

Tôi sẽ dùng version nào

Trong phỏng vấn, version backtracking với visited array. Nó là dễ đọc nhất trong ba cách implement "thực sự", invariant tường minh, và mở rộng trực tiếp sang các biến thể có pruning. Tôi có thể viết từ trí nhớ trong khoảng hai phút và giải thích trong khi code.

Với code production ở Python khi tôi chỉ cần output và không bao giờ cần sửa logic liệt kê, itertools.permutations ổn. Nó đã được test, nhanh, và một dòng.

Version swap tôi dùng khi bộ nhớ hạn chế và n lớn hơn — thực tế điều đó thường có nghĩa là một bài toán thuộc nhóm khác, vì n=6 theo constraint ở đây làm sự phân biệt không đáng kể.

Vị trí bài này trong series backtracking

Đây là seriesOrder 3, sau Subsets (78) và Combination Sum (39). Subsets giới thiệu mô hình rẽ nhánh include/exclude nơi bạn đưa ra quyết định nhị phân ở mỗi phần tử. Combination Sum giới thiệu pruning bị ràng buộc bởi target cắt cành sớm. Permutations giới thiệu pattern visited-set: mọi phần tử đều có thể ở mọi level, nên bạn cần bookkeeping tường minh để tránh dùng lại.

Bốn bài gần nhất:

• LeetCode 47 — Permutations II: cùng hình dạng, nhưng nums có thể chứa phần tử trùng lặp. Thêm bước sort và điều kiện "skip nếu cùng giá trị với sibling trước" trong vòng lặp. Mảng used vẫn còn; nó có thêm một guard phụ.
• LeetCode 77 — Combinations: chọn k phần tử từ [1..n] mà không quan tâm thứ tự. Dùng skeleton backtracking nhưng duyệt từ chỉ số start (không phải toàn bộ mảng) để tránh đếm cùng một tập hợp hai lần.
• LeetCode 39 — Combination Sum: chọn phần tử có tổng bằng target; phần tử có thể dùng lại. Thêm điều kiện pruning (remaining < 0 -> return) làm cây hữu hạn kể cả với lặp lại.
• LeetCode 17 — Letter Combinations of a Phone Number: sinh tất cả chuỗi từ bảng chữ cái nhiều level. Cùng pattern DFS, nhưng mỗi level duyệt qua một tập ký tự khác thay vì một pool chung.

Mental model cơ bản qua tất cả bài này là như nhau: một cây quyết định trong đó mỗi nút là một đáp án một phần, mỗi cạnh là một lựa chọn, và algorithm là DFS thu thập các đường đi hoàn chỉnh. Permutations là version gọn nhất của model đó.