Problem 1: Coin Change

Link to the problem: https://leetcode.com/problems/coin-change/

class Solution {

    private int answer(int[] coins, int amount, HashMap<Integer, Integer> map){
        if(amount<0) return -1;
        if(amount==0) return 0;
        if(map.containsKey(amount)) return map.get(amount);
        int res = -1;
        for(int i:coins){
            int n = answer(coins, amount-i, map);
            if(n!=-1){
                if(res==-1) res = n;
                else res = Math.min(res, n);
            }
        }
        if(res==-1){
            map.put(amount, -1);
            return -1;
        }else{
            map.put(amount, res+1);
            return res+1;
        }
    }

    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        Arrays.sort(coins);
        int start = 0;
        int end = coins.length - 1;
        while (start < end) {
            int temp = coins[start];
            coins[start] = coins[end];
            coins[end] = temp;
            start++;
            end--;
        }
        return answer(coins, amount, map);
    }
}

---

Problem 2: Partition Equal Subset Sum

Link to the problem: https://leetcode.com/problems/partition-equal-subset-sum/

class Solution {

    static HashMap<Integer, Boolean> map;

    private boolean answer(ArrayList<Integer> list, int sum, int target){
        System.out.println(sum);
        if(sum<target) return false;
        if(sum==target) return true;
        if(map.containsKey(sum)) return map.get(sum);
        ArrayList<Integer> l = (ArrayList<Integer>) list.clone();
        for(Integer i:l){
            ArrayList<Integer> temp = (ArrayList<Integer>) l.clone();
            temp.remove(i);
            boolean bool = answer(temp, sum-i, target);
            map.put(sum, bool);
            if(bool) break;
        }
        return map.getOrDefault(sum, false);
    }

    public boolean canPartition(int[] nums){
        int sum = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i:nums) {
            list.add(i);
            sum+=i;
        }
        if(sum%2!=0) return false;
        map = new HashMap<>();
        Collections.sort(list);
        Collections.reverse(list);
        int target = sum/2;
        return answer(list, sum, target);
    }
}

---

Problem 3: Combination Sum IV

Link to the problem: https://leetcode.com/problems/combination-sum-iv/

class Solution {

    HashMap<Integer, Integer> map;
    int res = 0;

    private int answer(int[] nums, int target){
        if(target<0) return -1;
        if(map.containsKey(target)) return map.get(target);
        if(target==0){
            return 1;
        }
        int num = 0;
        for(int i:nums){
            int temp = answer(nums, target-i), res;
            if(temp!=-1) num+=temp;
        }
        map.put(target, num);
        return num;
    }

    public int combinationSum4(int[] nums, int target) {
        map = new HashMap<>();
        Arrays.sort(nums);
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int temp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = temp;
        }
        return answer(nums, target);
    }
}

---

Problem 4: Unique Paths

Link to the problem: https://leetcode.com/problems/unique-paths/

class Solution {

    private int answer(int[][] arr, int m, int n){
        if(arr[m][n]!=-1) return arr[m][n];
        if(m<0 || n<0) return 0;
        if(m==0 || n==0) return 1;
        arr[m][n] = answer(arr, m-1, n) + answer(arr, m, n-1);
        return arr[m][n];
    }

    public int uniquePaths(int m, int n) {
        int[][] arr = new int[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++) arr[i][j]=-1;
        }
        return answer(arr, m-1, n-1);
    }
}

---

Problem 5: Decompress Run-Length Encoded List

Link to the problem: https://leetcode.com/problems/decompress-run-length-encoded-list/

class Solution {
    public int[] decompressRLElist(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            int freq = nums[i];
            int val = nums[++i];
            while(freq-->0) list.add(val);
        }
        int[] res = new int[list.size()];
        for(int i=0; i<list.size(); i++) res[i] = ((Integer) list.get(i)).intValue();
        return res;
    }
}

---