Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Menu Combination Sum
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//'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; } }
[
+
]
Show input
Compilation time: 0.84 sec, absolute running time: 0.15 sec, cpu time: 0.12 sec, memory peak: 18 Mb, absolute service time: 0,99 sec
edit mode
|
history
|
discussion
[] [[2.0, 5.03], [3.01, 4.02]]