题解 | #牛群分组II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    private final List<List<Integer>> result = new ArrayList<>();
    private int[] candidates;
    private int target;
    public int[][] cowCombinationSum2 (int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        dfs(new ArrayList<>(), 0, 0);
        int[][] res = new int[result.size()][];
        // 集合转数组
        for (int i = 0; i < result.size(); i++) {
            res[i] = new int[result.get(i).size()];
            for (int j = 0; j < res[i].length; j++) {
                res[i][j] = result.get(i).get(j);
            }
        }
        return res;
    }
    public void dfs(List<Integer> path, int sum, int idx) {
        // 判断和是否大于等于target
        if (sum >= target) {
            // 如果等于，就添加到集合中
            if (sum == target) result.add(path);
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            // 将元素添加的数组中
            path.add(candidates[i]);
            // 递归搜索下一个位置
            dfs(new ArrayList<>(path), sum + candidates[i], i + 1);
            // 回溯，移除最后一个添加的元素
            path.remove(path.size() - 1);
        }
    }
}

本题知识点分析：

1.递归+回溯

2.数学模拟

3.深度优先搜索

4.数组遍历

5.集合转数组

本题解题思路分析：

1.判断和是否大于等于target

2.如果等于，就添加到集合中

3.将元素添加的数组中

4. 递归搜索下一个位置

5.回溯，移除最后一个添加的元素

6.将集合转数组发挥

本题使用编程语言: Java