题解 | #加起来和为目标值的组合#

package org.example.test;

import com.alibaba.fastjson.JSONObject;

import java.util.*;

public class CombinationSumTest {
    public static void main(String[] args) {
        CombinationSumTest test = new CombinationSumTest();
        int[] num = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        LinkedList<Integer> ret = new LinkedList<>();
        Arrays.sort(num);
        test.doCombinationSum2(num, 20, ret, 0);
        System.out.println(test.ans + "==");
    }

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

    public void doCombinationSum2(int[] num, int target, LinkedList<Integer> ret, int m) {
        if (target == 0) {
            ans.add(new ArrayList<>(ret));
            return;
        }
        for (int i = m; i < num.length; i++) {
            if (i > m && num[i] == num[i - 1]) continue; // 很关键，这个考得有点牵强
            if (num[i] <= target) {
                ret.add(num[i]);
                doCombinationSum2(num, target - num[i], ret, i + 1);
                ret.removeLast();
            }
        }
    }


    public void doCombinationSum3(int[] num, int target) {
        LinkedList<ArrayList<ArrayList<Integer>>> result = new LinkedList<>();
        ArrayList<ArrayList<Integer>> first = new ArrayList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(num[0]);
        first.add(arrayList);
        result.add(first);
        for (int i = 1; i < num.length; i++) {
            ArrayList<Integer> f = new ArrayList<>();
            f.add(num[i]);
            ArrayList<ArrayList<Integer>> secend = new ArrayList<>();
            secend.add(f);
            ArrayList<ArrayList<Integer>> t = result.getLast();
            for (ArrayList<Integer> ret : t) {
                ArrayList<Integer> t1 = new ArrayList<>(ret);
                t1.add(num[i]);
                secend.add(t1);
                secend.add(ret);
            }
            result.add(secend);
            result.removeFirst();
        }
        System.out.println(result.getLast().size());
        for (ArrayList<Integer> ret : result.getLast()) {
            System.out.println(JSONObject.toJSONString(ret));
            int sum = ret.stream().mapToInt((a) -> a).sum();
            if (sum == target) {
                Collections.sort(ret);
                if (!ans.contains(ret)) {
                    ans.add(new ArrayList<>(ret));
                }
            }
        }
        ans.sort(new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                StringBuilder a = new StringBuilder();
                StringBuilder b = new StringBuilder();
                for (Integer value : o1) {
                    a.append(value);
                }
                for (Integer value : o2) {
                    b.append(value);
                }
                return a.toString().compareTo(b.toString());
            }
        });
    }
}