Quay lui (Backtracking)

def permutations(nums):
    result = []
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # Backtrack
    
    backtrack([], nums)
    return result

fun permutations(nums: List<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    
    fun backtrack(path: MutableList<Int>, remaining: List<Int>) {
        if (remaining.isEmpty()) {
            result.add(path.toList())
            return
        }
        
        for (i in remaining.indices) {
            path.add(remaining[i])
            backtrack(path, remaining.filterIndexed { idx, _ -> idx != i })
            path.removeAt(path.size - 1)
        }
    }
    
    backtrack(mutableListOf(), nums)
    return result
}

List<List<int>> permutations(List<int> nums) {
  List<List<int>> result = [];
  
  void backtrack(List<int> path, List<int> remaining) {
    if (remaining.isEmpty) {
      result.add(List.from(path));
      return;
    }
    
    for (int i = 0; i < remaining.length; i++) {
      path.add(remaining[i]);
      backtrack(path, [...remaining.sublist(0, i), ...remaining.sublist(i + 1)]);
      path.removeLast();
    }
  }
  
  backtrack([], nums);
  return result;
}

func permutations(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    
    func backtrack(_ path: inout [Int], _ remaining: [Int]) {
        if remaining.isEmpty {
            result.append(path)
            return
        }
        
        for i in remaining.indices {
            path.append(remaining[i])
            var newRemaining = remaining
            newRemaining.remove(at: i)
            backtrack(&path, newRemaining)
            path.removeLast()
        }
    }
    
    var path = [Int]()
    backtrack(&path, nums)
    return result
}

List<List<Integer>> permutations(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
}
 
void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        path.add(nums[i]);
        used[i] = true;
        backtrack(result, path, nums, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

def solve_n_queens(n):
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_safe(row, col):
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return result

fun solveNQueens(n: Int): List<List<String>> {
    val result = mutableListOf<List<String>>()
    val board = Array(n) { CharArray(n) { '.' } }
    
    fun isSafe(row: Int, col: Int): Boolean {
        for (i in 0 until row) if (board[i][col] == 'Q') return false
        var i = row - 1; var j = col - 1
        while (i >= 0 && j >= 0) if (board[i--][j--] == 'Q') return false
        i = row - 1; j = col + 1
        while (i >= 0 && j < n) if (board[i--][j++] == 'Q') return false
        return true
    }
    
    fun backtrack(row: Int) {
        if (row == n) {
            result.add(board.map { String(it) })
            return
        }
        for (col in 0 until n) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
            }
        }
    }
    
    backtrack(0)
    return result
}

List<List<String>> solveNQueens(int n) {
  List<List<String>> result = [];
  List<List<String>> board = List.generate(n, (_) => List.filled(n, '.'));
  
  bool isSafe(int row, int col) {
    for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
      if (board[i][j] == 'Q') return false;
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
      if (board[i][j] == 'Q') return false;
    return true;
  }
  
  void backtrack(int row) {
    if (row == n) {
      result.add(board.map((r) => r.join()).toList());
      return;
    }
    for (int col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }
  
  backtrack(0);
  return result;
}

func solveNQueens(_ n: Int) -> [[String]] {
    var result = [[String]]()
    var board = Array(repeating: Array(repeating: Character("."), count: n), count: n)
    
    func isSafe(_ row: Int, _ col: Int) -> Bool {
        for i in 0..<row { if board[i][col] == "Q" { return false } }
        var i = row - 1, j = col - 1
        while i >= 0 && j >= 0 { if board[i][j] == "Q" { return false }; i -= 1; j -= 1 }
        i = row - 1; j = col + 1
        while i >= 0 && j < n { if board[i][j] == "Q" { return false }; i -= 1; j += 1 }
        return true
    }
    
    func backtrack(_ row: Int) {
        if row == n {
            result.append(board.map { String($0) })
            return
        }
        for col in 0..<n {
            if isSafe(row, col) {
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."
            }
        }
    }
    
    backtrack(0)
    return result
}

List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(result, board, 0);
    return result;
}
 
void backtrack(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
        result.add(Arrays.stream(board).map(String::new).toList());
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(result, board, row + 1);
            board[row][col] = '.';
        }
    }
}