What leads to duplicate results?


  • 0
    R

    Below is my code, it is a typical NP-problem code.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
    
            for(int i=0;i<candidates.length;i++){
                List<Integer> line = new ArrayList<Integer>();
                calc(target,0,i,candidates,line,res);
            }
            return res;
            
        }
        
        public void calc(int target, int prev, int beacon, int[] a,  List<Integer> line, List<List<Integer>> res){
            if(prev<target){
                for(int i=beacon;i<a.length;i++){
                    if(i>0&&a[i]==a[i-1])
                    continue;
                    
                    int curr = prev+a[i];
                    List<Integer> li = new ArrayList<Integer>(line);
    
                    if(curr==target){
                        li.add(a[i]);
                        res.add(li);
                    } else if(curr<target){
                        li.add(a[i]);
                        calc(target,curr,i,a,li,res);
                    }
                }
               
            }
        }
    

    However, when the input is [1,2], it will generate a result with duplicate:
    Output: [[1,1],[2],[2]]
    Expected: [[1,1],[2]]
    I could not figure out why there is another[2], can anyone help?
    Thanks in advance.


Log in to reply
 

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