Why backtracking is giving wrong results in case of 1st question and correct results for 2nd. Leetcode #322 #78 respectively

Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

import java.util.Arrays;

class Solution {
    static final int MAX_INF = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int[] arr : dp) {
            Arrays.fill(arr, -1);
        }
        int res = minCoinsReq(coins, amount, n,new ArrayList<Integer>(), dp);
        if (res == MAX_INF -1) {
            return -1;
        }
        return res;
    }

  public int minCoinsReq(int[] coins, int amount, int n, ArrayList<Integer> curCoinsList, int[][] dp){  
     if(amount ==0){
        return curCoinsList.size();
     } 
       if(n==0){
        return MAX_INF-1;
    }
    if(dp[n][amount]!=-1 ){
        return dp[n][amount];
    }
    if(coins[n-1]<=amount){
        int coinAtIdxNotIncluded = minCoinsReq(coins,amount,n-1,curCoinsList,dp);
        curCoinsList.add(coins[n-1];)
        int coinAtIdxIncluded = minCoinsReq(coins,amount-coins[n-1],n, curCoinsList,dp);
        curCoinsList.remove(curCoinsList.size()-1);
        return dp[n][amount]= Math.min(coinAtIdxIncluded,coinAtIdxNotIncluded);
    }else {
         return dp[n][amount]= minCoinsReq(coins,amount,n-1, curCoinsList,dp);
      
    }
   }
}

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

class Solution {
public List<List<Integer>> subsets(int[] nums) {
    Set<List<Integer>> result = new HashSet<>();
    addSubsetsRec(nums, result, new ArrayList<Integer>(), 0);
    return new ArrayList<>(result);
}

public void addSubsetsRec(int[] nums, Set<List<Integer>> result, List<Integer> currentList, int idx) {
    if (idx == nums.length) {
        result.add(new ArrayList<>(currentList));
        return;
    }
    
    // Exclude current element
    addSubsetsRec(nums, result, currentList, idx + 1);

    // Include current element
    currentList.add(nums[idx]);
    addSubsetsRec(nums, result, currentList, idx + 1);

    // Backtrack to remove the recently added element
    currentList.remove(currentList.size() - 1);
}

}

Answer 1

• The base cases are incorrect.
• Also, the dp has not been properly populated.
• The recursive calls for updating the current coins list are not properly handled.

Code

import java.util.Arrays;

class Solution {
    static final int MAX_INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = { 1, 2, 5 };
        int amount = 11;
        int result = solution.coinChange(coins, amount);
        System.out.println(result);
    }

    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int[] arr : dp) {
            Arrays.fill(arr, -1);
        }
        int res = minCoinsReq(coins, amount, n, dp);
        if (res == MAX_INF - 1) {
            return -1;
        }
        return res;
    }

    public int minCoinsReq(int[] coins, int amount, int n, int[][] dp) {
        if (amount == 0) {
            return 0;
        }
        if (n == 0) {
            return MAX_INF - 1;
        }
        if (dp[n][amount] != -1) {
            return dp[n][amount];
        }
        if (coins[n - 1] <= amount) {
            int coinAtIdxNotIncluded = minCoinsReq(coins, amount, n - 1, dp);
            int coinAtIdxIncluded = minCoinsReq(coins, amount - coins[n - 1], n, dp);
            if (coinAtIdxIncluded != MAX_INF - 1) {
                coinAtIdxIncluded++;
            }
            return dp[n][amount] = Math.min(coinAtIdxIncluded, coinAtIdxNotIncluded);
        } else {
            return dp[n][amount] = minCoinsReq(coins, amount, n - 1, dp);
        }
    }
}

---

Notes:

• The curCoinsList maintains a list of current coins used to reach the target amount, but its being updated incorrectly. The curCoinsList should add/remove the coins used so far in the current possible path. When a coin is included in the current path, it should be added to the list, and when backtracking, it should be removed.

• The recursive calls should be performed such that the correct state is passed to each call and the backtracking is performed properly.