Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
recursive solution for subset 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
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace Rextester { public class Program { //recursive solution for subset sum public static void Main(string[] args) { int[] values = { 3, 34, 4, 12, 5, 2 }; int sum = 46; int n = values.Length; if (isSubsetSum(values, n, sum) == true) Console.WriteLine("Found a subset with given sum"); else Console.WriteLine("No subset found for given sum"); } // Returns true if sum of sub ser is equal to given sum static bool isSubsetSum(int[] values, int n, int sum) { // Base Cases - if sum is 0, it is true if (sum == 0) { return true; } //if there are no values, retrun false if (n == 0 && sum != 0) { return false; } // If last element is greater than sum, then ignore it if (values[n - 1] > sum) return isSubsetSum(values, n - 1, sum); /* else, check if sum can be obtained by any of the following (a) including the last element (b) excluding the last element */ return isSubsetSum(values, n - 1, sum) || isSubsetSum(values, n - 1, sum - values[n - 1]); } } }
Show compiler warnings
[
+
]
Show input
Compilation time: 0,41 sec, absolute running time: 0,46 sec, cpu time: 0,36 sec, average memory usage: 18 Mb, average nr of threads: 3, absolute service time: 0,94 sec
edit mode
|
history
|
discussion
Found a subset with given sum