组合总数[标准回溯 + 回溯技巧--降低栈深度]

前言

对于排列组合问题，一般用DFS搜索，状态规划来空间换时间，减少没必要的重复计算。回溯常见技巧，将数组排序，大数/小数先行，降低函数栈深度；回溯常见技巧剪枝，降低运行时间。

一、组合总数

二、标准回溯

1、搜索回溯

// 组合总和
public class CombinationSum {
    
    /* target：给一些候选数字，然后无限用，取和为target的组合情况。 dfs不断寻找即可（无重复元素，无零元素），当和 大于等于 target时则递归结束 | 所用元素用完时递归结束。 */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        // dfs寻找
        dfs(candidates, 0,0, target, ans, el);
        // ans已填充满
        return ans;
    }

    private void dfs(int[] candidates, int cur,int sum, int target, List<List<Integer>> ans, List<Integer> el) {
    
        if (sum >= target) {
    
            if (sum == target)
                ans.add(new ArrayList<>(el));
            return;
        }
        // 标准回溯
        for(int i = cur;i < candidates.length;i++){
    
            el.add(candidates[i]);
            dfs(candidates,i,sum + candidates[i],target,ans,el);
            el.remove(el.size() - 1);
        }
    }
}

2、降低栈深度

// 让递归深度变浅一点，通过逆序来实现。
class CombinationSum2 {
    
    /* target：给一些候选数字，然后无限用，取和为target的组合情况。 dfs不断寻找即可（无重复元素，无零元素），当和 大于等于 target时则递归结束 | 所用元素用完时递归结束。 */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        // 先给candidates排个序，让大数先行，从而快速剪枝，降低函数栈深度。
        Arrays.sort(candidates);
        // dfs寻找
        dfs(candidates, candidates.length - 1,0, target, ans, el);
        // ans已填充满
        return ans;
    }

    private void dfs(int[] candidates, int cur,int sum, int target, List<List<Integer>> ans, List<Integer> el) {
    
        if (sum >= target) {
    
            if (sum == target)
                ans.add(new ArrayList<>(el));
            return;
        }
        // 标准回溯
        for(int i = cur;i >= 0;i--){
    
            el.add(candidates[i]);
            dfs(candidates,i,sum + candidates[i],target,ans,el);
            el.remove(el.size() - 1);
        }
    }
}

总结

1）标准回溯，DFS与动规。
2）排序降低栈深度与剪枝。

参考文献

[1] LeetCode 组合总数