package com.company;

import java.util.*;

class Solution {
    Map<String, Set<List<Integer>>> mp;
    int[] nums;

    Set<List<Integer>> impl(int start, int target) {
        String key = "" + start + "_" + target;
        if (mp.containsKey(key)) {
            return mp.get(key);
        }

        Set<List<Integer>> ret;
        if (start < nums.length) {
            ret = new HashSet<>();
            ret.addAll(impl(start+1, target));
        }
        else {
            ret = new HashSet<>();
        }

        if (start > 0) {
            if (target == nums[start - 1]) {
                List<Integer> item = new ArrayList<>();
                item.add(nums[start - 1]);
                //print(item, 1);
                ret.add(item);
            }
            else if (start < nums.length && target > nums[start - 1]) {
                Set<List<Integer>> tmpRet = impl(start + 1, target - nums[start - 1]);
                Iterator<List<Integer>> iter = tmpRet.iterator();
                while (iter.hasNext()) {
                    List<Integer> item = new ArrayList<>(iter.next());
                    //print(item, 2);
                    item.add(nums[start - 1]);
                    Collections.sort(item);

                    //print(item, 3);
                    //System.out.println("Start " + start + " target " + target);
                    ret.add(item);
                }
            }
        }

        /*System.out.println("Begin ret:" + key);
        Iterator<List<Integer>> iter = ret.iterator();
        while (iter.hasNext()) {
            print(iter.next(), 4);
        }
        System.out.println("End ret:" + key);*/
        mp.put(key, ret);
        return ret;
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        nums = candidates;
        mp = new HashMap<>();
        List<List<Integer>> ret = new ArrayList<>();
        if (candidates.length == 0) {
            return ret;
        }

        impl(0, target);
        String key = "" + 0 + "_" + target;
        ret = new ArrayList<>(mp.get(key));
        return ret;
    }

    void print(List<Integer> item, int flag) {
        System.out.printf("Here %d:", flag);
        Iterator iter = item.iterator();
        while (iter.hasNext()) {
            System.out.printf("%d,", iter.next());
        }
        System.out.println();
    }
}

public class Main {

    public static void main(String[] args) {
        System.out.println("Hello!");
        Solution solution = new Solution();

        int[] cand = {10,1,2,7,6,1,5};
        int target = 8;
        List<List<Integer>> ret = solution.combinationSum2(cand, 8);
        System.out.printf("Get ret: %s\n", ret.size());

        Iterator<List<Integer>> iterator = ret.iterator();
        while (iterator.hasNext()) {
            Iterator iter = iterator.next().iterator();
            while (iter.hasNext()) {
                System.out.printf("%d,", iter.next());
            }
            System.out.println();
        }

        System.out.println();

    }
}