// Input: nothing for the default test cases // or two lines of space separate integers. // The first line is the list to process. // The second line should have two numbers: // the set size and the maximum sum. // Duplicates list values are ignored. // Created for this code golf challenge: // https://codegolf.stackexchange.com/q/193245 // Given a sequence of numbers, print out all // possible sets such that the sum is less // than a number // The problem has 3 inputs. // L: a list of all numbers // size: the size each set can be // max: the max sum amongst each set // The challenge is as follows: // Given L, size and max, construct as many // sets from L such that the number of elements // is size and the sum of each of the elements // does not exceed max. // Examples: // func(L=[1,2,3,4], size=2, max=5) = [{1,2}, // {1,3}, {2,3}, {1,4}] // Notice how each of the values in the // outputted set are sum <= max. // func(L=[1,2,3,4], size=3, max=6) = [{1,2,3}] // func(L=[1,2,3,4], size=3, max=5) = [{}] or // empty list, whichever you want // Note that in the set you cannot have // duplicated items. ie: {2,1} = {1,2} // Constraints on inputs: // L: 0 or more elements // size: 0 <= size <= len(L) // max: 0 or more // If a list has 0 items, then always return // the empty set. // If the size is 0, then always return the // empty set. // If max is 0, it is possible that there are // negative values in L, in which case the // returned sets need not be empty. // Shorted bytes wins! // Expanded function with comments to process // our challenge. Parameters are our list, // set size, and maximum sum. fun process(list: List, size: Int, max: Int) { // Allocate an empty result list and // convert to set and back to list to // toss duplicates. val result = MutableList(0) { "" } val available = list.toSet().toList() // Recursive function to generate the // output. Parameters are the nesting // still needed, the first index to begin // with, our total sum so far, and the // elements we used so far. fun recurse(nests: Int, begin: Int, total: Int, used: List) { // If our recursion is done and our // sum is less or equal to our maximum, // convert our used list to a string and // add it to our results. if (nests < 1) { if (total <= max) result.add(used.joinToString(",", "{", "}")) // Otherwise, we need more elements in // our set so for any remaining indexes, // recurse. } else for (element in begin..available.size-1) recurse(nests-1, element+1, total+available[element], used+listOf(available[element])) } // recurse // Start our recursion and display our // results. recurse(size, 0, 0, List(0) { 0 }) println(result.joinToString(",", "[", "]")) } // process // Compressed function to process our challenge. // Must be a function to use recursion. See // expanded version for comments. // 286 bytes fun p(l:List,s:Int,m:Int){val r=MutableList(0){""} val a=l.toSet().toList() fun r(n:Int,b:Int,t:Int,u:List){if(n<1){if(t<=m)r.add(u.joinToString(",","{","}"))}else for(e in b..a.size-1)r(n-1,e+1,t+a[e],u+listOf(a[e]))} r(s,0,0,List(0){0}) println(r.joinToString(",","[","]"))} // Function to display the inputs prior to // running our process. Parameters are our // list, set size, and maximum sum. fun display(list: List, size: Int, max: Int) { print("(L=$list, size=$size, max=$max)=") p(list, size, max) } // display // Main function created for this challenge. fun main(args: Array) { // Try reading the user's test case. Read // the first line, split on the spaces, // and convert to integers for the list. // Read the second line, split on the // spaces, and convert to integers for the // set size and maximum sum. Cause an // exception on end of file, non integers, // or not having two integers on the // second line. Otherwise, process the // user's test case. try { val list = readLine()!!.split(" ").map { it.toInt() } val data = readLine()!!.split(" ").map { it.toInt() } if (data.size != 2) throw IllegalArgumentException( "Bad input!") display(list, data[0], data[1]) // On exception, complain and process our // test cases. } catch (error: Throwable) { println("Bad input using defaults!") display(listOf(1, 2, 3, 4), 2, 5) display(listOf(1, 2, 3, 4), 3, 6) display(listOf(1, 2, 3, 4, 1, 1, 2), 3, 5) } // try } // main

sets cg