题解 | #牛群分组II#

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<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // 排序，方便剪枝

        backtrack(candidates, target, 0, new ArrayList<>(), result);
        int[][] array = new int[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            List<Integer> sublist = result.get(i);
            array[i] = new int[sublist.size()];
            for (int j = 0; j < sublist.size(); j++) {
                array[i][j] = sublist.get(j);
            }
            
        }
        return array;
        }

        private void backtrack(int[] candidates, int target, int start,
                               List<Integer> current, List<List<Integer>> result) {
            if (target < 0) {
                return;
            }
            if (target == 0) {
                result.add(new ArrayList<>(current));
                return;
            }

            for (int i = start; i < candidates.length; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue; // 跳过重复元素，避免重复组合
                }
                current.add(candidates[i]);
                backtrack(candidates, target - candidates[i], i + 1, current,
                          result); // 注意：i + 1 表示不重复选取同一个元素
                current.remove(current.size() - 1); // 回溯
            }
        }
    }

知识点：

1. 回溯法：一种通过逐步构建解决方案空间来求解问题的方法。
2. 排序：对 candidates 数组进行排序，可以方便后续的剪枝操作。
3. 剪枝：在搜索过程中通过条件判断，跳过无效的搜索分支，提高效率。

解题思路：

首先对 candidates 数组进行排序，以便于后续的剪枝操作。然后，我们使用回溯法来搜索所有可能的组合。对于每个位置的元素，我们有两种选择：选择当前元素或者不选择。在回溯过程中，我们通过剪枝操作排除一些无效的分支，从而提高搜索效率。需要注意的是，我们要避免选择重复的元素，以及在结果集中避免重复的组合。在循环遍历 candidates 数组时，我们使用 i > start && candidates[i] == candidates[i - 1] 来判断是否重复，从而跳过重复元素。