Total number of combinations [standard backtracking + backtracking techniques -- reducing stack depth]

Preface

For permutation and combination problems , It's usually used DFS Search for , State planning changes space for time , Reduce unnecessary double counting . Back to common techniques , Sort the array , Large number / Decimal first , Reduce the function stack depth ; Back to common techniques pruning , Reduce running time .

One 、 Total number of combinations

Two 、 Standard backtracking

1、 Search backtracking

//  Combinatorial summation 
public class CombinationSum {
    
    /* target： Give some candidate numbers , Then unlimited use , Take and for target The combination of . dfs Just keep looking （ No repeating elements , No zero element ）, When and   Greater than or equal to  target Recursion ends when  |  Recursion ends when all elements used are used up . */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        // dfs seek 
        dfs(candidates, 0,0, target, ans, el);
        // ans Full 
        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;
        }
        //  Standard backtracking 
        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、 Reduce stack depth

//  Make the recursion depth a little lighter , By reversing the order .
class CombinationSum2 {
    
    /* target： Give some candidate numbers , Then unlimited use , Take and for target The combination of . dfs Just keep looking （ No repeating elements , No zero element ）, When and   Greater than or equal to  target Recursion ends when  |  Recursion ends when all elements used are used up . */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        //  First give candidates Make a sequence , Let big numbers go first , To quickly prune , Reduce the function stack depth .
        Arrays.sort(candidates);
        // dfs seek 
        dfs(candidates, candidates.length - 1,0, target, ans, el);
        // ans Full 
        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;
        }
        //  Standard backtracking 
        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);
        }
    }
}

summary

1） Standard backtracking ,DFS And dynamic gauge .
2） Sorting reduces stack depth and prunes .

reference

[1] LeetCode Total number of combinations