LeetCode39. 组合总和

• 算法
  • 题目要求：可以重复使用数字，解集唯一
  • 1.排序数组
  • 2.遍历数组的每个数，当作一个解的第一个数，然后依然从当前位置（可以重复使用数字）递归寻找子结果
    • 2.1 遍历到target小于数组中的值时不会有解，停止遍历
    • 2.2 遍历到target等于数组中的值时即发现一个解，下面不可能存在解（数组由小到大排序），停止遍历
    • ps：避免解集重复，当遍历的位置是开始的第一个位置或者不等于它上一个位置时才算上这一个数
  • 3.遍历每一个子结果，和解的第一个数合并即是一个解，很多个子结果合并即是解集

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    return combinationSum(candidates, 0, target);
}

private List<List<Integer>> combinationSum(int[] candidates, int begin, int target) {
    List<List<Integer>> result = new ArrayList<>(10);
    for (int i = begin; i < candidates.length; i++) {
        if (i == begin || candidates[i] != candidates[i-1]) {
            if (candidates[i] < target) {
                List<List<Integer>> subResult = combinationSum(candidates, i, target-candidates[i]);
                for (List<Integer> list : subResult) {
                    ArrayList<Integer> aResult = new ArrayList<>(10);
                    aResult.add(candidates[i]);
                    for (int x : list) {
                        aResult.add(x);
                    }
                    result.add(aResult);
                }
            } else if (candidates[i] == target) {
                ArrayList<Integer> subResult = new ArrayList<>(10);
                subResult.add(candidates[i]);
                result.add(subResult);
                break;
            } else {
                break;
            }
        }
    }
    return result;
}

LeetCode40. 组合总和 II

• 算法
  • 题目要求：不可以重复使用数字，解集唯一
  • 1.排序数组
  • 2.遍历数组的每个数，当作一个解的第一个数，然后从下一位置（不能重复使用数字）递归寻找子结果
    • 2.1 遍历到target小于数组中的值时不会有解，停止遍历
    • 2.2 遍历到target等于数组中的值时即发现一个解，下面不可能存在解（数组由小到大排序），停止遍历
    • ps：避免解集重复，当遍历的位置是开始的第一个位置或者不等于它上一个位置时才算上这一个数
  • 3.遍历每一个子结果，和解的第一个数合并即是一个解，很多个子结果合并即是解集

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    return combinationSum2(candidates, 0, target);
}

private List<List<Integer>> combinationSum2(int[] candidates, int begin, int target) {
    List<List<Integer>> result = new ArrayList<>(10);
    for (int i = begin; i < candidates.length; i++) {
        if (i == begin || candidates[i] != candidates[i-1]) {
            if (candidates[i] < target) {
                List<List<Integer>> subResult = combinationSum2(candidates, i+1, target-candidates[i]);
                for (List<Integer> list : subResult) {
                    ArrayList<Integer> aResult = new ArrayList<>(10);
                    aResult.add(candidates[i]);
                    for (int x : list) {
                        aResult.add(x);
                    }
                    result.add(aResult);
                }
            } else if (candidates[i] == target) {
                ArrayList<Integer> subResult = new ArrayList<>(10);
                subResult.add(candidates[i]);
                result.add(subResult);
                break;
            } else {
                break;
            }
        }
    }
    return result;
}