Tricoloring an array of integers
Apart from some obvious mistakes ($j is overwritten by the for loop, right after the assignment), you are only looking at cases where values are exactly one third of the sum, while there are also the cases where this value can only be reached by adding different values together.
The first check would be that the sum of values is a multiple of 3 (like you already did).
You could then use a recursive algorithm, where at each level of recursion you look at a next value in the array, and decide whether to assign the color red to it (yes or no).
If at a certain moment you reach the required sum ( 1/3 of total), you continue the recursion, but starting again from the first value, and then deciding whether to assign the color green to one particular value in the array (yes or no). Of course, you cannot assign green when red was already assigned to it, so in that case there is not really a decision (it is a no).
If then again you can achieve the required sum, you have a solution: all the non-assigned values will be blue.
Here is such implementation:
function solution($arr) {
$sum = array_sum($arr);
if ($sum % 3) return "impossible";
$division = $sum / 3;
function recurse(&$arr, &$result, $division, $color, $sum, $i) {
if ($sum === $division) {
// We got the right sum for one color.
// If this was the second color, we have a solution
if ($color === "G") return true;
// If this was the first color (R), then now assign the second (G).
// Don't assign Green before the first Red, as that would be just
// an inversion of colors. Our solution will have B before the first
// R, and R before the first G.
$first = array_search("R", $result);
return recurse($arr, $result, $division, "G", 0, $first+1);
}
if ($i >= count($arr)) return false; // failed to match the division
// First, try without coloring this value:
$success = recurse($arr, $result, $division, $color, $sum, $i+1);
if ($success) return true;
// Secondly, try coloring this value, if it was not yet colored (blue is default):
if ($result[$i] === "B") {
$result[$i] = $color;
$success = recurse($arr, $result, $division, $color, $sum + $arr[$i], $i+1);
if ($success) return true;
$result[$i] = "B"; // Set back to default color
}
// No luck. Backtrack
return false;
}
// Initialise the solution array with only blue values
$result = array_fill(0, count($arr), "B"); // Fill with default color (i.e. "B");
if ($division === 0) return $result; // no need to look further
// Recurse to assign red to some values, and after that: green to some other values, but let the first value stay assigned to blue (as it could be any).
$success = recurse($arr, $result, $division, "R", 0, 1);
return $success ? implode($result, "") : "impossible";
}
// Sample run:
$arr = array(3, 7, 2, 5, 4);
$result = solution($arr);
echo $result . "\n";
See it run on repl.it;
The notion of time complexity in terms of N is meaningless, since N is at most 18. But if we for a moment ignore the limitation on N, the time complexity is determined by the fact that all configurations are looked at that have any of the three colors at each index.
There is an insignificant optimisation that will make the algorithm only look at configurations where a B is assigned to the first value, and R is assigned to the first value that is not assigned to B.
So this would make it run in O(3N).
I Don't code in php but have the solution in JS, if it helps. Working demo here.
let fillColor = (colored, arr, requiredSum, currVal, color) => {
let added = false
for(let idx =0; idx<colored.length; idx++) {
if (!colored[idx]) { // iterate over only those idx which are not colored.
let tempSum = currVal + arr[idx];
if (tempSum === requiredSum) { // exit if colored;
added = true;
colored[idx] = color;
break;
} else if (tempSum < requiredSum) { // if coloring not completed;
let newColored = [...colored]
newColored[idx] = color;
let retColored = fillColor(newColored, arr, requiredSum, tempSum, color)
if (retColored) {
added = true;
colored = retColored
break;
}
}
}
};
return added ? colored : false;
}
let solution = (arr) => {
let colored = new Array(arr.length)
// Number of colors, R, G, B
let k = 3
let arrSum = arr.reduce((a,b) => a+b, 0);
// See if sum of array is divisible by k;
if (arrSum%k === 0 && arr.length >= k) {
let requiredSumOfSubset = arrSum / k;
colored = fillColor(colored, arr, requiredSumOfSubset, 0, 'R')
colored = fillColor(colored, arr, requiredSumOfSubset, 0, 'G')
colored = fillColor(colored, arr, requiredSumOfSubset, 0, 'B')
if (colored) {
// Print colored string
console.log(colored.join(''));
} else {
console.log("can't be colored equally");
}
} else {
console.log("impossible to tri-color");
}
}
// Some test cases.
solution([5,3,7,2,4]);
solution([3,2,1]); // can't be colored even though sum is divisible by 3
solution([5,5,5]);
solution([4,5]); // impossible to color even though sum is divisible by 3
solution([4,5,7]); // impossible to color;
solution([5,2,5,1,4,1,3]);
Here goes my solution in Java.
Explanation: this is an NP-complete problem, known as multiway number partitioning. It's the problem of partitioning a multiset (set that can repeat values) into K numbers of subsets, such that each subset sums to X.
In this case, we have a multiset that we want to partition in 3 subsets, such that each subset sums to the sum of the multiset divided by the number of subsets, 3. For this, I used a variation of the subset sum problem, which uses a backtracking algorithm to find those subsets. Since the subset problem finds ALL the sets (this means, a number of the original array can be in 2 or more subsets), we need to keep track of which numbers we are using on the original array, so that we don't use them again.
class SubsetSum {
//Track found subsets that sums X
static Vector<Vector<Integer>> subsets = new Vector<>(new Vector<>());
static int count = 0;
static int totalSubsets = 0;
// Returns true if there is a subset
// of set[] with sum equal to given sum
static boolean isSubsetSum(int[] set,
int n, int sum, Vector<Integer> subset)
{
// Base Cases: if we found a subset, we remove it from the set
if (sum == 0){
subsets.add(new Vector<>());
for (Integer integer : subset) {
subsets.get(count).add(integer);
removeElement(set, integer);
totalSubsets += integer;
}
count++;
return true;
}
if (n == 0) {
return false;
}
// If last element is greater than
// sum, then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum, subset);
/* else, check if sum can be obtained
by any of the following
(a) including the last element
(b) excluding the last element */
boolean exclude = isSubsetSum(set, n - 1, sum, subset);
Vector<Integer> v1 = new Vector<>(subset);
v1.add(set[n - 1]);
boolean include = isSubsetSum(set, n - 1, sum - set[n - 1], v1);
return exclude || include;
}
public static void main(String[] args)
{
int[] set = { 3, 7, 2, 5, 4, 1, 1, 1, 2,2,2,3,3,3,4,4,4, 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3 };
Date now = new Date();
System.out.println("elements in array: " + set.length);
int prom = sumElements(set) / 3;
System.out.println(subSetProblem(set, prom));
System.out.println("finished in: " + (new Date().getTime() - now.getTime()) + " ms");
}
private static void removeElement(int[] arr, int el) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == el){
arr[i] = Integer.MAX_VALUE;
break;
}
}
}
private static String subSetProblem(int[] set, int sum) {
int n = set.length;
Vector<Integer> subSet = new Vector<>();
char[] res = new char[set.length];
char[] colors = {'R', 'G', 'B'};
int col = 0;
int sumSet = sumElements(set);
//First we find the subsets. Since we modify the set in the recursion, we need to copy it to use the original array after.
if (isSubsetSum(Arrays.copyOf(set,set.length), n, sum, subSet) && sumSet == totalSubsets) {
for (Vector<Integer> v: subsets) {
System.out.println("Found a subset"
+ " with given sum: " + v);
//Now we color the final array according to the subsets
for (Integer i : v) {
res[indexOfIntArray(set, i)] = colors[col];
count++;
}
col++;
}
}
else {
return "Impossible";
}
return new String(res);
}
private static int sumElements(int[] set) {
int res = 0;
for (int i : set) {
res += i;
}
return res;
}
public static int indexOfIntArray(int[] array, int key) {
int res = -1;
for (int i = 0; i < array.length; ++i) {
if (key == array[i]) {
res = i;
array[i] = Integer.MAX_VALUE;
break;
}
}
return res;
}
The idea behind the algorithm is that we need to check if a number is either included in the solution, or excluded. If it's included, then we add the number into our subset, and substract its value from the sum. If we reach 0, then we found a valid subset, we add it to our subsets and remove those elements from our set, and keep recursing.
Note that, as mentioned on previous posts, this algorithm runs in O(3ⁿ). I added time measurements to track how fast this is, and for arrays of size arround 50 stills runs pretty fast.