Total number of combinations ii[each element can only be solved by + once]

Preface

Seek arrangement and combination , Half are backtracking searches , Use techniques to reduce recursion stack depth , Use pruning to reduce running time . Total number of combinations II Compared with directly finding the combination sum as target, The difference is that each element can only be used once , And need to remove the weight （ Because the same element in the array is selected more than once ）.

One 、 Total number of combinations II

Two 、 Backtracking search + duplicate removal

package everyday.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//  Total number of combinations II
public class CombinationSum3 {
    
    /* target: from candidates Select a number from the array , Let its sum be target, Each number can only be used once in a combination .  It is also a standard backtracking , But the difference is that next time cur Add 1, instead of cur, Because each number can only be selected once . */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        //  General techniques for standard backtracking 1： Sort a sortable array , Let big numbers go first , And then with pruning , Reduce recursion stack depth .
        Arrays.sort(candidates);
        //  Backtracking search to fill in matching combinations .
        dfs(candidates, candidates.length - 1, 0, target, el, ans);
        //  Returns the filled combination .
        return ans;
    }

    private void dfs(int[] candidates, int cur, int sum, int target, List<Integer> el, List<List<Integer>> ans) {
    
        //  When sum  Greater than or equal to  target  when , End recursion , Recursive export 1.
        if (sum >= target) {
    
            if (sum == target) ans.add(new ArrayList<>(el));
            return;
        }
        //  Recursive export 2： Element used up .
        // bug2: When there are the same elements , Will result in multiple repeated combinations .
        int pre = 1 << 31;
        for (int i = cur; i >= 0; i--) {
    
            if (pre == candidates[i]) continue;
            //  Standard backtracking .
            el.add(candidates[i]);
            // bug1:cur Bits often write cur - 1, Should write i - 1, Select the variables for each round i.
            dfs(candidates, i - 1, sum + candidates[i], target, el, ans);
            el.remove(el.size() - 1);
            //  to update pre, Prevent the same elements from forming duplicate sets .
            pre = candidates[i];
        }
    }
}

summary

1） Standard backtracking search exercise .
2） Backtracking techniques and pruning exercises .
3） How to go heavy , And some common problems in backtracking bug.

reference

[1] LeetCode Total number of combinations II