回朔算法是使用遞歸的方式，遍歷所有的狀態(tài)蛮原，一般借助數(shù)組等結(jié)構(gòu)進(jìn)行“剪枝”卧须，較少遍歷的次數(shù)。

解決的是 子集、組合故慈、排列 問題板熊。注意邊界條件。
子集和排列和順序無關(guān)察绷，要借助位置信息防止重復(fù)干签；
排列和位置無關(guān)，只需判斷輔助數(shù)據(jù)結(jié)構(gòu)（path）中是否包含當(dāng)前元素

下文介紹這幾種的標(biāo)準(zhǔn)代碼拆撼。

1容劳、子集

力扣78題：給你一個整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 闸度。返回該數(shù)組所有可能的子集（冪集）竭贩。

class Solution {

    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new ArrayList();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    // 注意index的用法
    public void dfs(int[] nums, int index) {
        res.add(new ArrayList(path));
        for(int i=index;i<nums.length;i++) {
            path.add(nums[i]);
            dfs(nums, i+1);
            path.remove(path.size()-1);
        }
    }
}

2、組合

組合是在子集的基礎(chǔ)上進(jìn)行剪枝莺禁，過程中不匹配直接返回留量，不在繼續(xù)遞歸。
力扣77：給定兩個整數(shù) n 和 k哟冬，返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合楼熄。

class Solution {

    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new ArrayList();

    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }

    public void dfs(int n, int k, int index) {
        // 剪枝：組合是特定的子集，保留符合的
        if(k == path.size()) {
            res.add(new ArrayList(path));
            return ;
        }
        for(int i=index;i<=n;i++) {
            path.add(i);
            dfs(n, k, i+1);
            path.remove(path.size()-1);
        }
    }
}

3浩峡、排列

力扣46題： 全排列 給定一個不含重復(fù)數(shù)字的數(shù)組 nums 可岂，返回其 所有可能的全排列 。你可以 按任意順序 返回答案翰灾。

class Solution {

    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new ArrayList();

    public List<List<Integer>> permute(int[] nums) {
        dfs(nums);
        return res;
    }

    public void dfs(int[] nums) {
        if(path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if(path.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            dfs(nums);
            path.remove(path.size()-1);
        }

    }
}