“This is the first day of my participation in the Gwen Challenge in November. See details of the event: The last Gwen Challenge in 2021”.

Sum of combinations II

Description: Given an array of candidates and a target number, find all combinations of the candidates that can be sum as target.

Each number in the candidates must be used only once in each combination.

Description:

  • All numbers, including the target number, are positive integers.
  • The solution set cannot contain repeated combinations.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution one: backtracking algorithm

  • First, sort the original array;

  • Then, declare an array freq to record the number of occurrences of each different number;

  • Then, the backtracking algorithm is used to recursively judge whether the processed sequences meet the conditions, and the sequences that meet the conditions are added to the result set. Finally, all the result sets that meet the conditions are returned.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode_040 {
    /** * records the number of occurrences of each different number */
    private static List<int[]> freq = new ArrayList<>();
    /** * The result set that meets the criteria */
    private static List<List<Integer>> ans = new ArrayList<>();
    /** * matching sequence */
    private static List<Integer> sequence = new ArrayList<>();

    /** * backtracking algorithm **@param candidates
     * @param target
     * @return* /
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // First sort the given array
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if(freq.isEmpty() || num ! = freq.get(size -1) [0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1) [1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public static void dfs(int pos, int rest) {
        if (rest == 0) {
            /** * If the current sum already equals target, add the current sequence to the result set */
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            /** * If all numbers have been traversed or the number to be processed is less than the next number to be matched, the current sequence is ineligible and */ is returned
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1); }}public static void main(String[] args) {
        int[] candidates = new int[] {10.1.2.7.6.1.5};
        for (List<Integer> integers : combinationSum2(candidates, 8)) {
            for (Integer integer : integers) {
                System.out.print(integer + ""); } System.out.println(); }}}Copy the code

Go up and look far, not to be seen by the whole world, but to see the whole world.