The OJ of this problem couldn't detect duplicated combinations


  • 0
    L

    The following code generates duplicated combinations on test case [2,2,2,3,4] with target=5.

    But it it got accepted.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        
        return getCombination(candidates, 0, target);
    }
    
    public static List<List<Integer>> getCombination(int[] array, int start, int target) {
    	
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        
        if (target < 0){
            return rst;
        }
        
        if (target == 0){
            rst.add(new ArrayList<Integer>());
            return rst;
        }
        
        for(int i=start; i<array.length; i++) {
        	
        	for(List<Integer> x : getCombination(array, i, target-array[i])){
                x.add(0, array[i]);
                rst.add(x);
            }
        }
        return rst;
         
     }

  • 0
    J

    I also find this problem. Maybe the question "assumes" that the input array does not contain duplicated elements. In your test case, [2,2,2,3,4], the number 2 appears three times.

    The solution to this problem is easy. After sorting the input array, we should delete the duplicated elements and make sure each element appears only once in the input array.


  • 0
    Q

    See Combination Sum II


Log in to reply
 

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