1.全排列

List<List<Integer>> res = new LinkedList<>();

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

2.八皇后

vector<vector<string>> res;

/* 输入棋盘边长 n，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
    // ‘.‘ 表示空，‘Q‘ 表示皇后，初始化空棋盘。
    vector<string> board(n, string(n, ‘.‘));
    backtrack(board, 0);
    return res;
}

// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
        res.push_back(board);
        return;
    }

    int n = board[row].size();
    for (int col = 0; col < n; col++) {
        // 排除不合法选择
        if (!isValid(board, row, col)) 
            continue;
        // 做选择
        board[row][col] = ‘Q‘;
        // 进入下一行决策
        backtrack(board, row + 1);
        // 撤销选择
        board[row][col] = ‘.‘;
    }
}

/* 是否可以在 board[row][col] 放置皇后？ */
bool isValid(vector<string>& board, int row, int col) {
    int n = board.size();
    // 检查列是否有皇后互相冲突
    for (int i = 0; i < n; i++) {
        if (board[i][col] == ‘Q‘)
            return false;
    }
    // 检查右上方是否有皇后互相冲突
    for (int i = row - 1, j = col + 1; 
            i >= 0 && j < n; i--, j++) {
        if (board[i][j] == ‘Q‘)
            return false;
    }
    // 检查左上方是否有皇后互相冲突
    for (int i = row - 1, j = col - 1;
            i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == ‘Q‘)
            return false;
    }
    return true;
}

// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
        res.push_back(board);
        return true;
    }
    ...
    for (int col = 0; col < n; col++) {
        ...
        board[row][col] = ‘Q‘;

        if (backtrack(board, row + 1))
            return true;

        board[row][col] = ‘.‘;
    }

    return false;
}

3.求子集

List<List<Integer>> res;
LinkedList<Integer> track = new LinkedList<>();
List<List<Integer>> subsets(List<Integer> nums) {
    // 记录走过的路径
    List<Integer> track;
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, 0, track);
    return res;
}

void backtrack(List<Integer> nums, int start, List<Integer> track) {
    res.add(track);
    // 注意 i 从 start 开始递增
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.add(nums[i]);
        // 回溯
        backtrack(nums, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rs = new ArrayList<>();
        builderSubSet(nums,rs);
        rs.add(new ArrayList<Integer>());//最后添加一个空集
        return rs;
    }
    //求数组nums的所有非空子集，存于rs中
    public void builderSubSet(int[] nums,List<List<Integer>> rs){
        //递归终结条件，只有一个元素，它的非空子集就是自己，直接添加到rs
        if(nums.length == 1){
            rs.add(Arrays.asList(nums[0]));
        }else if(nums.length>1){
        	//递归求解前n-1个元素的非空子集
            builderSubSet(Arrays.copyOf(nums,nums.length-1),rs);
            //前n-1个元素的非空子集求解完毕，处理第n个元素
            int size = rs.size();//获取当前子集的个数
            //将第n个子集也添加到rs
            rs.add(Arrays.asList(nums[nums.length-1]));
            //依次复制出当前子集，并为每一子集添加第n个元素，
            //之后再将这些子集添加到rs中
            List<Integer> clone;
            for(int i = 0;i<size;i++){
                clone = new ArrayList<>();
                for(Integer it : rs.get(i)) clone.add(it);
                clone.add(nums[nums.length-1]);
                rs.add(clone);
            }
        }
    }
}

非递归：

public class Main {
    public static void main(String[] args) {
        int[] a = {1,2,3};
        buildSubSet(a).forEach(System.out::println);
    }

    public static List<List<Integer>> buildSubSet(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        //先添加一个空集
        result.add(new ArrayList<>());
        for (int i = 0;i<nums.length;i++){
            //获取当前子集个数
            int size = result.size();
            //依次取出当前子集并为每一子集添加元素nums[i]
            //最后再添加回result
            for (int j = 0;j<size;j++){
                List<Integer> clone = new ArrayList<>(result.get(j));
                clone.add(nums[i]);
                result.add(clone);
            }
        }
        return result;
    }
}

4.组合

vector<vector<int>>res;

vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n <= 0) return res;
    vector<int> track;
    backtrack(n, k, 1, track);
    return res;
}

void backtrack(int n, int k, int start, vector<int>& track) {
    // 到达树的底部
    if (k == track.size()) {
        res.push_back(track);
        return;
    }
    // 注意 i 从 start 开始递增
    for (int i = start; i <= n; i++) {
        // 做选择
        track.push_back(i);
        backtrack(n, k, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

回溯 排列 子集 组合

原文：https://www.cnblogs.com/ming-michelle/p/14646394.html