Java 题解 | #牛群分组II#

import java.util.*;


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

    public int[][] cowCombinationSum2(int[] candidates, int target) {
        dfs(candidates, 0, target);
        return convertTo2DArray(ans);
    }

    private void dfs(int[] candidates, int index, int target) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            path.add(candidates[i]);
            target -= candidates[i];
            dfs(candidates, i + 1, target);
            path.remove(path.size() - 1);
            target += candidates[i];
        }
    }

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

编程语言是Java。

该题考察的知识点是回溯算法，用于在给定的整数数组中找到所有组合，使得它们的和等于目标值。

通过递归回溯的方式，在数组中遍历每个元素，并根据当前元素是否选择、剩余目标值的大小来进行选择和回退操作，从而找到所有可能的组合。最后，将所有符合条件的组合转换为一个二维数组并返回。

算法的核心思想是通过深度优先搜索（DFS）来遍历各种可能的情况，同时利用递归和回溯的技巧，来确保所有可能性都被探索。