package com.sandao.sandaodemo.controller;

import java.util.*;

/**
 * @author sandao
 * Created on 2019/5/31.
 */
public class Super {
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5,13,45,64,23,2,4,67,12,34,22,1,5,78,90,3,45,67,3,2,6,87,4,2,67,8,4,2,45,67};
        int target = 23;
        long start = System.currentTimeMillis() ;
        Arrays.sort(nums);
        System.out.println(sum(target, nums));
        long end = System.currentTimeMillis() ;
        System.out.println(end-start);
    }

    private static Set<List<Integer>> sum(int target, int[] nums) {
        //map中 以当前和为key 所有可能的情况为value
        Map<Integer, Set<List<Integer>>> result = new HashMap<>(target * 2);

        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i];

            if (currentNum <= target){
                Map<Integer, Set<List<Integer>>> newResult = new HashMap<>(result);
                for (Integer key : result.keySet()) {
                    if (target >= currentNum + key) {
                        Set<List<Integer>> list = result.get(key);
                        Set<List<Integer>> newList = result.get(key + currentNum) != null ? new HashSet<>(result.get(key + currentNum)) : new HashSet<>();
                        //遍历原有的可能结果
                        for (List<Integer> listDetail : list) {
                            List<Integer> copyList = new LinkedList<>(listDetail);
                            copyList.add(currentNum);
                            newList.add(copyList);
                            newResult.put(currentNum + key, newList);
                        }
                    }
                }
                result = newResult;

                //放入当前数值的单个值
                List<Integer> currentList = new LinkedList<>();
                currentList.add(currentNum);
                Set<List<Integer>> currentSet = result.get(currentNum) != null ? result.get(currentNum) : new HashSet<>();
                currentSet.add(currentList);
                result.put(currentNum, currentSet);
            }else {
                break;
            }
        }
        return result.get(target);
    }
}