Loop Recursive Solution - Combination Sum II - DFS

Take the advantage of sorted. Sort the array first, then loop it recursively: outer is all elements in the array, and inner is begin position changes. result is also passed, so add one, call recursive, remove it. when add to results, remember to add a clone instead of adding a reference to result.

This way of programming can be used to all such problems, pass result reference and add clone to results when conditions satisfied. After recursive all, remove the one added in the same method. DFS!

A pre flag/value is set to avoid duplicates.  (1, 1, 3), never start from 1 all times. Update target in each iteration as well.

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if(num == null || num.length == 0){
            return results;
        }
        ArrayList<Integer> result = new ArrayList<Integer>();
        Arrays.sort(num);
        combinationOps(num, 0,  target, result, results);
        return results;
    }
   
    private void combinationOps(int[] num, int begin, int target, ArrayList<Integer> result, ArrayList<ArrayList<Integer>> results){
        if(target < 0){
            return;
        }else{
            if(target == 0){
                ArrayList<Integer> clone = new ArrayList<Integer>();
                clone.addAll(result);
                results.add(clone);
            }else{
                int pre = -1;
                for(int i = begin; i < num.length; i++){
                    if(num[i] != pre){
                        result.add(num[i]);
                        combinationOps(num, i + 1, target - num[i], result, results);
                        pre = num[i];
                        result.remove(result.size() - 1);
                    }
                }
            }
        }
    }
}