Provide another perspective of solving this problem.


  • 0
    A

    My solution is also a recursive solution. But it solves the problem from a different perspective.

    The most natural idea for solving this combination problem is using recursion.

    for each element, we either select or not select this element in the final result. This gives us many possible combinations. My approach as other many approach uses the same rules to filter many impossible combinations so that I wouldn't explain this part.

    The tricky part is to generate the distinct solutions without using HashSet, which means the code has already done redudanct calculation. To generate the distince results, the idea is to never explore the solution path twice. In the code, "path" is the soution path, if we have already added one element to the path. for the same path, we would never add the same element to the path again. we use "pre" to record the last element that we added so that we wouldn't add it again.

    public class Solution {
    public int NONEXIST = 0;
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        ArrayList<Integer> path = new ArrayList<Integer>();
        if(num.length == 0){
            return ret;
        }
        NONEXIST = num[0] - 1;
        searchCombination(num, 0, ret, target, path, NONEXIST);
        return ret;
    }
    public void searchCombination(int[] num, int i, List<List<Integer>> all, int remain, ArrayList<Integer> path, int pre){
        if(remain == 0){
            all.add(path);
            return;
        }
        if(i >= num.length){
            return;
        }
        if(remain < num[i]){
            return;
        }
        if(sum(num, i) < remain){
            return;
        }
        if(pre != num[i]){
            ArrayList<Integer> clonePath = new ArrayList<Integer>(path);
            clonePath.add(num[i]);
            searchCombination(num, i+1, all, remain-num[i], clonePath, NONEXIST);
            pre = num[i];
        }
        searchCombination(num, i+1, all, remain, path, pre);
    }
    public int sum(int[] num, int start){
        int ret = 0;
        for(int i = start; i < num.length; i++){
            ret += num[i];
        }
        return ret;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.