Trying to write, a method that computes from a list of 6 numbers, the sum of those of numbers that sum up to the target number, the rest of these numbers that can't produce the target should not be taken into account. Every number can be used at most once.
For example:
- If the
targetis12and a list of numbers is[6, 6, 6, 6, 6, 6]then return value should be36. - If we receive a list of numbers
[1, 3, 4, 5, 6, 6]and atargetis should be12(5 1 6=12and also5 4 3=12, however, numbers can only be used once and not reused, therefore only one of the combinations can contribute the result).
EDIT: Regarding the {6, 6, 6, 6, 6, 6} example, 6 6 = 12, and then if this is repeated we sum up that as well.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class MyClass {
public static void main(String args[]) {
ArrayList<Integer> numbers = new ArrayList<>(6);
numbers.add(1);
numbers.add(3);
numbers.add(4);
numbers.add(5);
numbers.add(6);
numbers.add(6);
System.out.println(sumRecursively(numbers, 0, 12, new ArrayList<Integer>()));
}
private static int sumRecursively(ArrayList<Integer> numbers, int sum, int target, ArrayList<Integer> partial) {
for(int i: partial) sum = i;
if(sum == target) { return sum; }
else {
for(int n = 0; n < numbers.size(); n) {
partial.add(numbers.remove(n));
sumRecursively(numbers, sum, target, partial);
}
}
return sum;
}
}
Description: numbers can be generated anything from 1-6, for each cell/index in array list of total six slots in space. Numbers can be anything between 1 to 6. However, the main concern is to try to sum up to target as long as it goes. When two or three or n-pairs have been used to sum a matching target, then remove all of them. Look at the remainders if any, see if they sum to target otherwise return the sum.
Furthermore, the target range is: 3-12, and 3 is presented by a LOW. Everything with LOW, is summed up to match 3.
My current solution does not work.
I wrote this function now:
private static int sumRecursively(ArrayList<Integer> numbers,
int sum, int target, int n) {
if(sum > target)
sum = 0;
if(sum == target) { return sum; }
sum = numbers.remove(n);
return sumRecursively(numbers, sum, target, n);
}
This method works with [1, 3, 4, 5, 6, 6] and gives 12, because summing everything up to the first 6, gives 13. However, if all are [6,6,6,6,6,6] for examples, then the sum becomes 12. Because, it does not continue on.
NOTE: If you've PLAYED the game Yahtzee then you know.
https://en.wikipedia.org/wiki/Yahtzee
New version:
private static int sumRecursively(ArrayList<Integer> numbers,
int sum, int target, int n, ArrayList<Integer> sums) {
if(sum > target)
sum = 0;
if(numbers.size() == 0) {
sums.add(sum);
return sums.stream().mapToInt(Integer::intValue).sum();
}
if(sum == target) { sums.add(sum); sum = 0; }
sum = numbers.remove(n);;
return sumRecursively(numbers, sum, target, n, sums);
}
Similar problems remain, e.g., [1,3,2,2,6,5] gives a 6 for target 12. For example, 1 5 6 = 12 here, or 3 2 2 5 = 12.
PROBLEM: This whole problem is about, figuring out, what combination of numbers in a list of total of 6 different numbers from 1-6, sum up to a target value. If potential candidates make up a sum, these candidates cannot be reused again. The remainders are checked for any possibility to sum up to the target value, if nothing is found, then the sum of the sums list containing all target values is returned. E.g., getting a list of 6 x 6, and target 6 6=12, 6 6=12 6 6=12 = then 36 should be the sum.
This code gives:
static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial)
{
int s = 0;
for (int x: partial) s = x;
if (s == target) {
System.out.println("sum(" Arrays.toString(partial.toArray()) ")=" target);
}
if (s >= target)
return;
for(int i=0;i<numbers.size();i ) {
ArrayList<Integer> remaining = new ArrayList<Integer>();
int n = numbers.get(i);
for (int j=i 1; j<numbers.size();j ) remaining.add(numbers.get(j));
ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
partial_rec.add(n);
sum_up_recursive(remaining,target,partial_rec);
}
}
static void sum_up(ArrayList<Integer> numbers, int target) {
sum_up_recursive(numbers,target,new ArrayList<Integer>());
}
Usage:
Integer[] numbers = {1,3,4,5,6,6};
sum_up(new ArrayList<Integer>(Arrays.asList(numbers)), 12);
Output:
sum([1, 5, 6])=12
sum([1, 5, 6])=12
sum([3, 4, 5])=12
sum([6, 6])=12
PROBLEM: How to make this stop, once, a combination is found, and make sure that not same numbers are reused.
CodePudding user response：
In order to ensure that all the elements in each combination are unique, we to track indices that have been already used. I.e. each time we find a combination which sums up to the target number, we should prohibit the usage of elements that have been used in this combination, but not earlier (because there can be many combinations which are not able to produce the target, and therefore any element should eligible to be used until we didn't construct a complete combination that gives the target using this element).
To track the elements that are taken, we need an object that would be visible in every recursive branch. And we are already passing a list of numbers while making every recursive call, what if we would modify it each time we found a combination that produces the target number by removing the elements that have been use in this combination? If we took this road after the first combination, thing would become complicated because we will not be able to rely on the indices (because they can change in an unpredictable way) while constructing a single combination - it's crucial to ensure that each element that belongs to a particular combination is used only once withing a combination. Since values of elements might be identical, we should use the iteration order to construct each combination properly, but each removal of elements would create a mess. So, is there a better way?
We can maintain an array of boolean values, each element is this array would indicate whether a number at a particular index already belongs to a combination that gives the target or not.
Instead of clattering the recursive method with the code that manipulates with this boolean array, I've encapsulated it within a class with simple and self-explanatory methods, and sumRecursively() makes use of an instance of this class.
public class CombinationTracker {
private boolean[] isUsed;
public CombinationTracker(int size) {
this.isUsed = new boolean[size];
}
public boolean indexIsUsed(int ind) {
return isUsed[ind];
}
public boolean allNotUsed(List<Integer> indices) {
// return indices.stream().noneMatch(i -> isUsed[i]); // this line does the same as the loop below
boolean result = true;
for (int idx: indices) {
if (isUsed[idx]) {
result = false;
break;
}
}
return result;
}
public void setIsUsed(List<Integer> indices) {
for (int ind: indices)
setIsUsed(ind);
}
public void setIsUsed(int ind) {
isUsed[ind] = true;
}
}
Using this approach, we are able to construct combinations from numbers that are not used yet, and iterate over the list of numbers starting from a particular position by passing the index while making a recursive call. We can be sure that any of the elements that reside prier to the current position would not be added to the current combination.
Now, a quick recap on recursion.
Every recursive implementation consists of two parts:
Base case - that represents an edge-case (or a set of edge-cases) for which the outcome is known in advance. For this problem, there are two edge-cases:
we've managed to find a combination that gives the target number, i.e.
currentSum == target, and the result would be equal totarget;the end of the list is reached (and the combination doesn't result to the target), the result would be
0(this edge-case resolves automatically by termination condition of theforloop in the recursive case, and therefore no need to treat it separately).
Recursive case - a part of a solution where recursive calls are made and where the main logic resides. In the recursive case we're iterating over the list of numbers and at each iteration step (if the index is not yet used) we are making one or two recursive calls depending on a value of the current element (depending whether we exceed the target or not). In the general, we have two opportunities: either take the current element, or ignore it. The results of these recursive calls would be added together and produce the return value of the recursive case.
Since we need a couple of additional parameters, it's a good practice to create an auxiliary overloaded method (that will be used in the client code) which expects only a list of numbers and a target value and delegates the actual work to the recursive method.
That's how it might look like.
public static int sumRecursively(List<Integer> numbers, int target) {
return sumRecursively(new ArrayList<>(numbers),
new ArrayList<>(),
new CombinationTracker(numbers.size()),
0, 0, target);
}
The actual recursive method:
private static int sumRecursively(List<Integer> numbers,
List<Integer> combination,
CombinationTracker tracker,
int currentIndex,
int currentSum, int target) {
if (currentSum == target && tracker.allNotUsed(combination)) { // base case - a combination has been found
tracker.setIsUsed(combination);
return target;
}
// recursive case
int result = 0;
for (int i = currentIndex; i < numbers.size(); i ) {
int next = numbers.get(i);
if (tracker.indexIsUsed(i)) continue;
if (currentSum next > target) continue;
// there are two opportunities for each number: either use next number, or ignore it
// add next number
if (next currentSum <= target) {
List<Integer> newCombination = new ArrayList<>(combination);
newCombination.add(i);
result = sumRecursively(numbers, newCombination, tracker, i 1, currentSum next, target);
}
// ignore next number
result = sumRecursively(numbers, new ArrayList<>(combination), tracker, i 1, currentSum, target);
}
return result;
}
main()
public static void main(String[] args) {
System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
System.out.println(sumRecursively(List.of(6, 6, 6, 6, 6, 6), 12));
}
Output:
12
36