题解 | #牛群分组II#

题目考察的知识点是：

递归回溯。

题目解答方法的文字分析：

每个数字只能选一次，要获取全部的方案，可以采用回溯的方法。从左到右选择是否把当前元素加入路径，当到达末尾或者累积总和大于等于要求时停止。当总和等于要求值时加入答案。由于我们优先选取当前元素的路径，所以得到字典序递增的答案。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    public static LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
    public int[][] cowCombinationSum2 (int[] candidates, int target) {
        // write code here
        Boolean[] flags = new Boolean[candidates.length];
        Arrays.fill(flags, false);
        search(candidates, target, 0, flags, new LinkedList<>());
        int[][] arr = new int[lists.size()][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[lists.get(i).size()];
            for (int j = 0; j < lists.get(i).size(); j++) {
                arr[i][j] = lists.get(i).get(j);
            }
        }
        return arr;
    }

    public void search(int[] nums, int target, int cur, Boolean[] flags,
                       LinkedList<Integer> arrayList) {
        if (cur == target) {
            lists.add(new LinkedList<>(arrayList));
            return;
        }
        for (int i = 0; i < flags.length; i++) {
            if (!flags[i]) {
                if (arrayList.size() != 0 && nums[i] < arrayList.get(arrayList.size() - 1)) {
                    continue;
                }
                arrayList.add(nums[i]);
                flags[i] = true;
                search(nums, target, cur + nums[i], flags, arrayList);
                arrayList.remove(arrayList.size() - 1);
                flags[i] = false;
            }
        }
    }
}