Backtracking to solve combinatorial problems

1. Combine （leetcode77）

Given n,k, from 1-n Choose from k Number

prune ： When the number of subsequent elements is insufficient , To reduce branches ,<=n-(k-path.length)+1

var combine = function(n, k) {
    let res = [],path=[];
    function combineHelper(n,k,startIndex){
        if(path.length == k){
            res.push([...path]);
            return;
        }
        for(let i = startIndex;i<=n-(k-path.length)+1;i++){
            path.push(i);
            combineHelper(n,k,i+1);
            path.pop();
        }
    }
    combineHelper(n,k,1);
    return res;
};

---

2. Total number of combinations III（leetcode216）

Find and for n Of k Number , Only 1-9

prune ： When the number of subsequent elements is insufficient , To reduce branches ,<=9-(k-path.length)+1

var combinationSum3 = function(k, n) {
    let path = [],res = [];
    function backtracking(start,sum){
        if(path.length == k){
            if(sum == n){
                res.push([...path]);
            }
            return;
        }
        //  Pruning 
        for(let i = start;i<=9-(k-path.length)+1;i++){
        // for(let i = start;i<=9;i++){
            path.push(i);
            backtracking(i+1,sum+i);
            path.pop();
        }
    }
    backtracking(1,0);
    return res;
};

---

3. Combinatorial summation （leetcode39）

From a non repeating array nums in , Find and target Array of

Be careful ： Array nums The elements in can be retrieved repeatedly

Pruning ： Prioritize , When nums[i]>target when , Pruning

var combinationSum = function(candidates, target) {
    let res = [],path = [];
    candidates.sort();
    function backtracking(j,sum){
        if(sum > target) return;
        if(sum == target){
            res.push([...path]);
            return;
        }
        for(let i = j;i<candidates.length;i++){
            const n = candidates[i];
            if(n>target-sum) continue;
            path.push(n);
            sum += n;
            // candidates The array in can be reused 
            backtracking(i,sum);
            path.pop();
            sum -= n;
        }
    }
    backtracking(0,0);
    return res;
};

---

4. Combinatorial summation III（leetcode40）

Duplicate array from nums in , Find and target Array of , Every nums[i] It can only be used once .Nums Repeat , but res Cannot have duplicate arrays in .

Be careful ： Array nums Elements in cannot be retrieved repeatedly

Pruning ： Prioritize , When nums[i]>target when , Pruning

duplicate removal ： Use used, De duplication of tree layer

var combinationSum2 = function(candidates, target) {
    let res = [],path = [];
    let len = candidates.length;
    candidates.sort((a,b)=>a-b);
    let used = new Array(len).fill(false);
    function backtrcking(startIndex,sum){
        if(sum > target) return;
        if(sum == target){
            res.push([...path]);
            return;
        }
        for(let i = startIndex;i<len;i++){
            let cur = candidates[i];
            if(cur >  target-sum || (i>0 && candidates[i] == candidates[i-1] && !used[i-1])) continue;
            if (used[i] == true) continue;
            path.push(cur);
            sum += cur;
            used[i] = true;
            backtrcking(i+1,sum);
            path.pop();
            sum -= cur;
            used[i] = false;
        }
    }
    backtrcking(0,0);
    return res;
};