preface

“This is the 16th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

  1. NC46 adds up to the combination of target values (medium)
  2. 216. Combined sum III
  3. 39. Combination sum

The sum is the combination of the target values

Description: Given a set of candidate numbers C and a target number T, find all combinations of candidates whose sum is equal to T.

Each number in C can be used only once in a combination.

Note:

  1. All the numbers in the problem (including the target number T) are positive integers \
  2. The numbers in the combination (A_1, a_2… , a_ka1, a2,… ,ak) should be ordered in non-decreasing order (A1 ≤ A2 ≤… Ak) or less
  3. The result must not contain duplicate combinations
  4. The order of indexes is compared from the smallest to the largest. The smaller index is ranked first. If the same index has the same value, the next index is compared.

Input:

,10,20,70,60,10,50 [100], 80Copy the code

The return value:

,20,50,10,60 [[10], [10], [10; seven], [20, 60]]Copy the code

Description:

The given candidate number set is [100,10,20,70,60,10,50] and the target number is 80Copy the code

Similar to subset problem II, the ending condition needs to be modified

Subset problem II

AC code:

    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    boolean used[];

    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        if (num == null || num.length == 0) {
            return new ArrayList<>();
        }
        Arrays.sort(num);
        used = new boolean[num.length];
        dfs(num, 0, target, new ArrayList<>());
        return ans;
    }

    void dfs(int[] num, int index, int target, ArrayList<Integer> temp) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = index; i < num.length; i++) {
            if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            temp.add(num[i]);
            dfs(num, i + 1, target - num[i], temp);
            temp.remove(temp.size() - 1);
            used[i] = false; }}Copy the code

216. Combined sum III

Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate numbers in each combination.

Description:

  • All numbers are positive integers.
  • The solution set must not contain duplicate combinations.

Similar to subset problem I, the ending condition needs to be modified

A subset of

If the number of elements in the temporary set is k, it will be added to the final result

AC code:

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k,n,1.new ArrayList<>());
        return ans;
    }

    void dfs(int k, int n, int index, List<Integer> temp) {
        if (temp.size() == k) {
            if (n == 0) {
                ans.add(new ArrayList<>(temp));
            }
            return;
        }

        for (int i = index; i < 10; i++) {
            temp.add(i);
            dfs(k, n - i, i + 1, temp);
            temp.remove(temp.size() - 1); }}Copy the code

39. Combination sum

Given an array of positive integers with no duplicate elements and a positive integer target, find all the unique combinations of digits in the candidates that can make the sum the target number.

The numbers in the candidates may be selected indefinitely. The two combinations are unique if at least one of the selected numbers differs in number.

For a given input, there are fewer than 150 unique combinations that guarantee that sum is target.

Similar to the subset problem I, because the numbers in the candidates can be selected indefinitely, so the optional conditions are different from before

AC code:

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target,0.new ArrayList<>());
        return ans;
    }

    void dfs(int[] candidates, int target, int index, List<Integer> temp) {
        if(target < 0) {return;
        }
        if(target == 0){
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            int val = candidates[i];
            temp.add(val);
            // Select * from I; // Select * from I
            dfs(candidates, target - val, i, temp);
            temp.remove(temp.size() - 1); }}Copy the code