Menu Combination Sum, Java

Menu Combination Sum

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester
{  
    private static final double eps = 1.0E-1;
    
    public static void main(String args[])
    {
        double[] prices = {2.40, 0.01, 6.00, 2.58};
        List<List<Double>> res = getCombos(prices, 2.50);
      
        System.out.println(res);
        prices = new double[]{10.02, 1.11, 2.22, 3.01, 4.02, 2.00, 5.03};
        List<List<Double>> combos = getCombos(prices, 7.03);
        System.out.println(combos);
        assert 2 == combos.size();
    }
    
    private static void dfs(List<List<Double>> res, List<Double> cur, double[] prices, int[] centPrices, int idx, int centTarget) {
        if(centTarget == 0) {
            res.add(new ArrayList<>(cur));
            return;
        }
        for(int i = idx; i < centPrices.length; i++) {
            if(centPrices[idx] == centPrices[i] && (idx != i)) continue;
            if(centPrices[i] > centTarget) break;
            cur.add(prices[i]);
            dfs(res, cur, prices, centPrices, i + 1, centTarget - centPrices[i]);
            if(cur.size() > 0) cur.remove(cur.size() - 1);
        }
        
    }
    
    
    private static List<List<Double>> getCombos(double[] prices, double target) {
        List<List<Double>> res = new ArrayList<>();
        if(prices == null || prices.length == 0) return res;
        Arrays.sort(prices);

int[] centPrices = new int[prices.length];
        for(int i = 0; i < prices.length; i++) {
            centPrices[i]= (int)Math.round(prices[i] * 100);
        }
        dfs(res, new ArrayList<Double>(), prices, centPrices, 0, (int)Math.round(target * 100));
        return res;
        
    }
}


run \| edit \| history \| help	0