数字组合 II

描述

给出一组候选数字(C)和目标数字(T),找出C中所有的组合,使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

注意事项
  • 所有的数字(包括目标数字)均为正整数。
  • 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
  • 解集不能包含重复的组合。
样例
给出一个例子,候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8  ,
解集为:[[1,7],[1,2,5],[2,6],[1,1,6]]

考察点
  • 回溯算法
    • 类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径
    • 选优搜索法,按选优条件向前搜索,以达到目标
  • 递归
    void backtrack(state s) {
    if(s is end){ // 当前结点为可行解
    sols.append(path); // 保存该解
    } else if(s has no ways){ // 当前结点为不可达叶子结点
    return;
    } else{ // 当前结点为中间结点
    for(i in possible ways){
    next_s = do i in s; // 选择一条边
    backtrack(next_s); // 在选择的边上往下走
    s = redo i in s; // 回溯到父结点
    }
    }
    }
答案
private List<List<Integer>> results;
public List<List<Integer>> combinationSum2(int[] num, int target) {
    num = bobbleSort(num);
    results = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    combinationSum2(num, target, 0, path, 0);

    return results;
}

public void combinationSum2(int[] num, int target, int sum, List<Integer> paths, int index) {
    int prev = -1;
    if (sum == target) {
        results.add(new ArrayList<Integer>(paths));
    } else if (sum > target || index >= num.length || paths.size() >= num.length) {
        return;
    } else {
        for (int i = index; i < num.length; i++) {
            if (num[i] != prev) {
                sum += num[i];
                paths.add(num[i]);
                i++;
                combinationSum2(num, target, sum, paths, i);
                i--;
                prev = num[i];
                paths.remove(paths.size() - 1);
                sum -= num[i];
            }
        }
    }
}

public int[] bobbleSort(int[] num) {
    for (int i = 0; i < num.length - 1; i++) {
        for (int j = num.length - 1; j > i; j--) {
            if (num[i] > num[j]) {
                int tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }
        }
    }
    return num;
}