题解 | #牛群分组II# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    List<Integer> path;
    List<List<Integer>> ans;

    public int[][] cowCombinationSum2(int[] candidates, int target) {
        path = new ArrayList<>();
        ans = new ArrayList<>();
        backtrace(candidates, target, 0, 0);
        return convertToArray(ans);
    }

    private void backtrace(int[] candidates, int target, int sum, int index) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length; ++i) {
            path.add(candidates[i]);
            backtrace(candidates, target, sum + candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }

    private int[][] convertToArray(List<List<Integer>> list) {
        int[][] result = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            List<Integer> sublist = list.get(i);
            result[i] = new int[sublist.size()];
            for (int j = 0; j < sublist.size(); j++) {
                result[i][j] = sublist.get(j);
            }
        }
        return result;
    }
}

使用的是Java语言。

该题考察的知识点是回溯算法和数组操作。

代码的文字解释如下：

• 在cowCombinationSum2方法中，初始化结果集ans和成员变量path。
• 调用backtrace方法开始回溯过程，初始索引为0，初始空列表。
• backtrace方法是核心的递归函数。在每一轮回溯中，从给定数组的开始位置开始遍历，如果当前元素小于等于目标值，则将其添加到组合中。然后继续递归调用backtrace方法，传递更新后的目标值和增加了一个元素的组合，以及当前元素的索引。当目标值等于0时，表示已生成一个满足条件的组合，将其添加到结果集中。回溯过程中，需要注意在递归结束后将最后一个添加的元素移除，以便尝试其他可能的组合。
• 在回溯完成后，通过convertToArray方法将结果集转换为二维数组，并返回作为最终结果。