679 24 Game

class Solution {
    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        for (int num : nums) list.add((double)num);
        return solve(list);
    }

    private boolean solve(List<Double> list){
        if (list.size() == 0) return false;
        if (list.size() == 1) return Math.abs(list.get(0) - 24) < 1e-6;

        for (int i = 0; i < list.size(); i++){
            for (int j = 0; j < list.size(); j++){
                if (i != j){
                    List<Double> list2 = new ArrayList<>();
                    for (int t = 0; t < list.size(); t++){
                        if (t != i && t != j) list2.add(list.get(t));
                    }

                    for (int k = 0; k < 4; k++){
                        if (k < 2 && j < i) continue;
                        if (k == 0){
                            list2.add(list.get(i) + list.get(j));
                        }
                        else if (k == 1){
                            list2.add(list.get(i) * list.get(j));
                        }
                        else if (k == 2){
                            list2.add(list.get(i) - list.get(j));
                        }
                        else{
                            if (list.get(j) != 0){
                                list2.add(list.get(i) / list.get(j));
                            }
                            else{
                                continue;
                            }
                        }
                        if (solve(list2)) return true;
                        list2.remove(list2.size() - 1);
                    }
                }
            }
        }

        return false;
    }
}

399 Evaluate Division

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, List<String>> pairs = new HashMap<>();
        Map<String, List<Double>> pairValues = new HashMap<>();

        for (int i = 0; i < equations.length; i++){
            String[] equation = equations[i];

            if (!pairs.containsKey(equation[0])){
                pairs.put(equation[0], new ArrayList<String>());
                pairValues.put(equation[0], new ArrayList<Double>());
            }
            if (!pairs.containsKey(equation[1])){
                pairs.put(equation[1], new ArrayList<String>());
                pairValues.put(equation[1], new ArrayList<Double>());
            }

            pairs.get(equation[0]).add(equation[1]);
            pairValues.get(equation[0]).add(values[i]);
            pairs.get(equation[1]).add(equation[0]);
            pairValues.get(equation[1]).add(1.0 / values[i]);
        }

        double[] ans = new double[queries.length];
        for (int i = 0; i < queries.length; i++){
            String[] query = queries[i];
            ans[i] = dfs(query[0], query[1], pairs, pairValues, new HashSet<String>(), 1.0);
            if (ans[i] == 0) ans[i] = -1.0;
        }

        return ans;
    }

    private double dfs(String start, String end, Map<String, List<String>> pairs, Map<String, List<Double>> pairValues, Set<String> set, double value){
        if (!pairs.containsKey(start)) return 0.0;
        if (set.contains(start)) return 0.0;
        if (start.equals(end)) return value;

        set.add(start);

        List<String> pairList = pairs.get(start);
        List<Double> valueList = pairValues.get(start);
        double temp = 0.0;
        for (int i = 0; i < pairList.size(); i++){
            temp = dfs(pairList.get(i), end, pairs, pairValues, set, value * valueList.get(i));
            if (temp != 0.0) break;
        }
        set.remove(start);
        return temp;
    }
}

638 Shopping Offers

class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        Map<List<Integer>, Integer> hash = new HashMap<>();
        return dfs(price, special, needs, hash);
    }

    private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, Map<List<Integer>, Integer> hash){
        if (hash.containsKey(needs)){
            return hash.get(needs);
        }

        int j = 0, res = dot(price, needs);
        for (List<Integer> s : special){
            ArrayList<Integer> clone = new ArrayList<>(needs);
            for (j = 0; j < needs.size(); j++){
                int diff = clone.get(j) - s.get(j);
                if (diff < 0) break;
                clone.set(j, diff);
            }
            if (j == needs.size()){
                res = Math.min(res, s.get(j) + dfs(price, special, clone, hash));
            }
        }
        hash.put(needs, res);

        return res;
    }

    private int dot(List<Integer> price, List<Integer> needs){
        int sum = 0;
        for (int i = 0; i < price.size(); i++){
            sum += price.get(i) * needs.get(i);
        }

        return sum;
    }
}

491 Increasing Subsequences

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        List<Integer> holder = new ArrayList<>();
        helper(res, holder, 0, nums);
        List<List<Integer>> ans = new ArrayList<>(res);
        return ans;
    }

    private void helper(Set<List<Integer>> res, List<Integer> holder, int index, int[] nums){
        if (holder.size() >= 2){
            res.add(new ArrayList<>(holder));
        }

        for (int i = index; i < nums.length; i++){
            if (holder.size() == 0 || holder.get(holder.size() - 1) <= nums[i]){
                holder.add(nums[i]);
                helper(res, holder, i + 1, nums);
                holder.remove(holder.size() - 1);
            }
        }
    }
}

473 Matchsticks to Square

public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 4 != 0) return false;

        Arrays.sort(nums);
        reverse(nums);

        return dfs(nums, new int[4], 0, sum / 4);
    }

    private boolean dfs(int[] nums, int[] sums, int index, int target) {
        if (index == nums.length) {
            if (sums[0] == target && sums[1] == target && sums[2] == target) {
            return true;
            }
            return false;
        }

        for (int i = 0; i < 4; i++) {
            if (sums[i] + nums[index] > target) continue;
            sums[i] += nums[index];
            if (dfs(nums, sums, index + 1, target)) return true;
            sums[i] -= nums[index];
        }

        return false;
    }

    private void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++; j--;
        }
    }
}