题解 | #牛群分组II# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    public int[][] cowCombinationSum2 (int[] candidates, int target) {
        // write code here
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        backtrace(candidates, target, 0, 0, path, ans);

        int[][] result = new int[ans.size()][];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = new int[ans.get(i).size()];
            for (int j = 0; j < ans.get(i).size(); j++) {
                result[i][j] = ans.get(i).get(j);
            }
        }

        return result;
    }

    private void backtrace(int[] candidates, int target, int sum, int index,
                           List<Integer> path, List<List<Integer>> ans) {
        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, ans);
            path.remove(path.size() - 1);
        }
    }
    }

编程语言是Java。

该题考察的知识点是回溯算法，通过递归和回溯的方式找到给定数组中所有的组合，使其和等于目标数。

代码简短的文字解释如下：

1. 调用 backtrace 方法进行回溯，传入整型数组 candidates、目标数 target、当前的和 sum、起始位置 index、组合列表 path，以及结果列表 ans。
2. 在 backtrace 方法中，首先判断如果当前的和 sum 大于目标数 target，则直接返回。
3. 如果当前的和 sum 等于目标数 target，则将当前的组合 path 加入结果列表 ans 中，然后返回。
4. 使用循环遍历数组 candidates，从指定的起始位置 index 开始。
5. 将当前数字 candidates[i] 添加到组合列表 path 中。
6. 递归调用 backtrace 方法，将目标数更新为 target，当前的和更新为 sum 加上当前数字 candidates[i]，起始位置更新为 i + 1，继续在剩余的数组中查找下一个数字的组合。
7. 每次递归返回后，将组合列表 path 的最后一个数字移除，以便尝试下一个数字的组合。
8. 最后将结果列表 ans 转换为二维数组并返回。