LeetCode每日一题：combination sum ii

问题描述

Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in C where the candidate numbers sums to T .
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a 1, a 2, … , a k) must be in non-descending order. (ie, a 1 ≤ a 2 ≤ … ≤ a k).
The solution set must not contain duplicate combinations.

For example, given candidate set10,1,2,7,6,1,5and target8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

问题分析

和上一题类似，由于这一题不能使用一个数多次，所以我们回溯的话从i+1开始，并且要进行去重操作。每次必须判断list是否已经存在result里面了才行。

代码实现

public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        backTrackingSum2(num, 0, target, list, result);
        return result;
    }

    private void backTrackingSum2(int[] num, int start, int target, ArrayList<Integer> list,
                                  ArrayList<ArrayList<Integer>> result) {
        if (target == 0) {
            boolean isExist = false;
            for (int i = result.size() - 1; i >= 0; i--) {
                ArrayList<Integer> exist = result.get(i);
                if (exist.equals(list)) {
                    isExist = true;
                    break;
                }
            }
            if (isExist == false) {
                result.add(new ArrayList<Integer>(list));
            }
            return;
        } else {
            for (int i = start; i < num.length && num[i] <= target; i++) {
                list.add(num[i]);
                backTrackingSum2(num, i + 1, target - num[i], list, result);
                list.remove(list.size() - 1);
            }
        }
    }