Java实现Combination Sum时重复组合问题求助

问题背景 #

给定整数数组和目标和B，找出数组中所有和为B的唯一组合，同一数字可多次选取，需满足：

• 所有数字均为正整数
• 组合元素按非降序排列（a₁ ≤ a₂ ≤ … ≤ aₖ）
• 组合本身按升序排列

示例输入输出：

输入:
N = 4
arr[] = {7,2,6,5}
B = 16

输出:
(2 2 2 2 2 2 2 2)
(2 2 2 2 2 6)
(2 2 2 5 5)
(2 2 5 7)
(2 2 6 6)
(2 7 7)
(5 5 6)

遇到的问题 #

当输入为arr[] = {8, 1, 8, 6, 8}, B = 12时，当前代码输出出现重复组合：
(1 1 1 1 1 1 1 1 1 1 1 1)(1 1 1 1 1 1 6)(1 1 1 1 8)(1 1 1 1 8)(1 1 1 1 8)(6 6)
正确输出应为：
(1 1 1 1 1 1 1 1 1 1 1 1)(1 1 1 1 1 1 6)(1 1 1 1 8)(6 6)

当前代码 #

static void findCombination(int idx, int target, int[] arr, ArrayList<ArrayList<Integer>> ans, List<Integer> ds){
        //base case
       
        if(idx == arr.length){
            if(target == 0){
                ans.add(new ArrayList<>(ds));
            }
            return;
        }
        //recursion
        if(arr[idx] <= target){
            ds.add(arr[idx]);
            findCombination(idx,target-arr[idx],arr,ans,ds); //function call
            ds.remove(ds.size()-1); //backtracking step
        }
        findCombination(idx+1,target,arr,ans,ds);
    }
    //Function to return a list of indexes denoting the required 
    //combinations whose sum is equal to given number.
    static ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int B)
    {
        // add your code here
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int[] arr = new int[A.size()];
        int i = 0;
        for(int val : A){
            arr[i++] = val;
        }
        Arrays.sort(arr);
        findCombination(0, B, arr, ans, new ArrayList<>());
        return ans;
    }
}

问题原因 #

当前代码仅对原数组做了排序，但原数组存在重复元素（比如多个8），递归过程中会对相同的元素重复处理，导致生成重复的组合。例如排序后的数组是[1,6,8,8,8]，当idx指向第一个8时，会生成包含8的组合；而idx指向第二个、第三个8时，又会重复生成相同的组合，因为这几个8的值完全一样。

解决方案 #

在递归跳过元素时，需要跳过所有与当前元素值相同的后续元素，避免重复处理。具体修改如下：

修改后的代码 #

import java.util.*;

public class Solution {
    static void findCombination(int idx, int target, int[] arr, ArrayList<ArrayList<Integer>> ans, List<Integer> ds){
        //base case
        if(target == 0){
            ans.add(new ArrayList<>(ds));
            return;
        }

        for(int i = idx; i < arr.length; i++){
            // 跳过重复元素，避免生成重复组合
            if(i > idx && arr[i] == arr[i-1]) continue;
            // 如果当前元素大于剩余目标，直接跳出（数组已排序，后续元素更大）
            if(arr[i] > target) break;

            ds.add(arr[i]);
            findCombination(i, target - arr[i], arr, ans, ds);
            ds.remove(ds.size()-1);
        }
    }

    static ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int B)
    {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        // 转换为数组并排序
        int[] arr = A.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(arr);
        findCombination(0, B, arr, ans, new ArrayList<>());
        return ans;
    }

    public static void main(String[] args) {
        ArrayList<Integer> A = new ArrayList<>(Arrays.asList(8,1,8,6,8));
        int B = 12;
        System.out.println(combinationSum(A, B));
    }
}

关键修改点 #

• 将原有的递归分支逻辑改为循环遍历，更方便处理重复元素的跳过
• 在循环中加入if(i > idx && arr[i] == arr[i-1]) continue;，跳过同一层递归中重复的元素
• 利用数组已排序的特性，当arr[i] > target时直接break，减少不必要的递归

这样修改后，就能避免生成重复的组合，得到正确的结果。

内容的提问来源于stack exchange，提问作者Fatima