4-Sum algorithm failing with duplicate values in Java

I'm trying to implement a 4-Sum algorithm in Java that works with duplicate values in the array. Here's my current attempt:

Specifically the problem:

Given and array a[] of n integers, the 4-sum problem is to determine if there exists distinct indices i, j, k and l such that a[i] + a[j] = a[k] + a[l].

So obviously int[] array = {1, 2, 1, 2, 3, 4}; passed to the fourSum method should satisfy the given problem and return true; It does return true until the array is sorted then returns false. Indices 0,1 = 3 and indices 2,3 = 3 so the method should find these and return true. I am not seeing the problem with the code.

debug output
Original array: [1, 2, 1, 2, 3, 4]
Array for checking: [1, 1, 2, 2, 3, 4]
Checking: 2 vs 4 at indices 0, 1, 2, 3
Checking: 2 vs 5 at indices 0, 1, 2, 4
Checking: 2 vs 6 at indices 0, 1, 2, 5
Checking: 2 vs 5 at indices 0, 1, 3, 4
Checking: 2 vs 6 at indices 0, 1, 3, 5
Checking: 2 vs 7 at indices 0, 1, 4, 5
Checking: 3 vs 5 at indices 0, 2, 3, 4
Checking: 3 vs 6 at indices 0, 2, 3, 5
Checking: 3 vs 7 at indices 0, 2, 4, 5
Checking: 3 vs 7 at indices 0, 3, 4, 5

I've tried:

Sorting the array first to group duplicates.
Skipping over duplicates in the loops to avoid redundant checks.

My questions are:

Why isn't this algorithm finding the correct 4-Sum combination?
Am I missing a logic step when handling duplicates?

import java.util.Arrays;

public class FourSum {

    public static boolean fourSum(int[] a) {
        int n = a.length;
        if (n < 4) {
            return false;
        }
        
     //   Arrays.sort(a);
        System.out.println("Array for checking: " + Arrays.toString(a));
        
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int sum1 = a[i] + a[j];
                        int sum2 = a[k] + a[l];
                        
                        // Debug print for every check
                        System.out.println("Checking: " + sum1 + " vs " + sum2 + " at indices " + i + ", " + j + ", " + k + ", " + l);
                        
                        // Specific check for our known solution
                        if (i == 0 && j == 2 && k == 1 && l == 3) {
                            System.out.println("KNOWN SOLUTION CHECK: " + sum1 + " vs " + sum2);
                        }
                        
                        if (sum1 == sum2) {
                            System.out.println("Found 4-SUM: " + a[i] + " + " + a[j] + " = " + a[k] + " + " + a[l] + " at indices " + i + ", " + j + ", " + k + ", " + l);
                            return true;
                        }
                    }
                }
            }
        }
        
        return false;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 1, 2, 3, 4};  // Example where 4-SUM condition should be met
        System.out.println("Original array: " + Arrays.toString(array));
        
        Arrays.sort(array);
        boolean resultSorted = fourSum(array);
        System.out.println("Result with sorting: " + resultSorted);
    }
}

I'm trying to implement a 4-Sum algorithm in Java that works with duplicate values in the array. Here's my current attempt:

Specifically the problem:

Given and array a[] of n integers, the 4-sum problem is to determine if there exists distinct indices i, j, k and l such that a[i] + a[j] = a[k] + a[l].

debug output
Original array: [1, 2, 1, 2, 3, 4]
Array for checking: [1, 1, 2, 2, 3, 4]
Checking: 2 vs 4 at indices 0, 1, 2, 3
Checking: 2 vs 5 at indices 0, 1, 2, 4
Checking: 2 vs 6 at indices 0, 1, 2, 5
Checking: 2 vs 5 at indices 0, 1, 3, 4
Checking: 2 vs 6 at indices 0, 1, 3, 5
Checking: 2 vs 7 at indices 0, 1, 4, 5
Checking: 3 vs 5 at indices 0, 2, 3, 4
Checking: 3 vs 6 at indices 0, 2, 3, 5
Checking: 3 vs 7 at indices 0, 2, 4, 5
Checking: 3 vs 7 at indices 0, 3, 4, 5

I've tried:

Sorting the array first to group duplicates.
Skipping over duplicates in the loops to avoid redundant checks.

My questions are:

Why isn't this algorithm finding the correct 4-Sum combination?
Am I missing a logic step when handling duplicates?

import java.util.Arrays;

public class FourSum {

    public static boolean fourSum(int[] a) {
        int n = a.length;
        if (n < 4) {
            return false;
        }
        
     //   Arrays.sort(a);
        System.out.println("Array for checking: " + Arrays.toString(a));
        
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int sum1 = a[i] + a[j];
                        int sum2 = a[k] + a[l];
                        
                        // Debug print for every check
                        System.out.println("Checking: " + sum1 + " vs " + sum2 + " at indices " + i + ", " + j + ", " + k + ", " + l);
                        
                        // Specific check for our known solution
                        if (i == 0 && j == 2 && k == 1 && l == 3) {
                            System.out.println("KNOWN SOLUTION CHECK: " + sum1 + " vs " + sum2);
                        }
                        
                        if (sum1 == sum2) {
                            System.out.println("Found 4-SUM: " + a[i] + " + " + a[j] + " = " + a[k] + " + " + a[l] + " at indices " + i + ", " + j + ", " + k + ", " + l);
                            return true;
                        }
                    }
                }
            }
        }
        
        return false;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 1, 2, 3, 4};  // Example where 4-SUM condition should be met
        System.out.println("Original array: " + Arrays.toString(array));
        
        Arrays.sort(array);
        boolean resultSorted = fourSum(array);
        System.out.println("Result with sorting: " + resultSorted);
    }
}

Share Improve this question edited Feb 3 at 9:00 Mark Rotteveel 110k229 gold badges156 silver badges225 bronze badges asked Feb 3 at 5:58 Anthony Pate 111 silver badge4 bronze badges

You never check index pairs like (0,2)-(1,3) or (0,3)-(1,2) – MBo Commented Feb 3 at 6:23
are you sure that the valid SUM will always comply to i < j < k < l ? And even more if the array is sorted! (simplest (counter) example I can think of [1, 1, 2, 2] -- a[0] + a[2] == a[1] + a[3]) – user85421 Commented Feb 3 at 7:56
(( basically what was given in first comment )) – user85421 Commented Feb 3 at 8:02

Add a comment |

1 Answer 1

Sorted by: Reset to default 1

The for loops in your algorithm do not cover all possibile indexes, so I suggest to change them from:

    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {

to:

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            for (int k = 0; k < n; k++) {
                if ((k == i) || (k == j)) continue;
                for (int l = 0; l < n; l++) {
                    if ((l == i) || (l == j) || (l == k)) continue;

With these loops you will run through all not-repeating indexes to perform the proper algorithm. Here is the result running the modified code:

Original array: [1, 2, 1, 2, 3, 4]
Array for checking: [1, 1, 2, 2, 3, 4]
Checking: 2 vs 4 at indices 0, 1, 2, 3
Checking: 2 vs 5 at indices 0, 1, 2, 4
Checking: 2 vs 6 at indices 0, 1, 2, 5
Checking: 2 vs 4 at indices 0, 1, 3, 2
Checking: 2 vs 5 at indices 0, 1, 3, 4
Checking: 2 vs 6 at indices 0, 1, 3, 5
Checking: 2 vs 5 at indices 0, 1, 4, 2
Checking: 2 vs 5 at indices 0, 1, 4, 3
Checking: 2 vs 7 at indices 0, 1, 4, 5
Checking: 2 vs 6 at indices 0, 1, 5, 2
Checking: 2 vs 6 at indices 0, 1, 5, 3
Checking: 2 vs 7 at indices 0, 1, 5, 4
Checking: 3 vs 3 at indices 0, 2, 1, 3
KNOWN SOLUTION CHECK: 3 vs 3
Found 4-SUM: 1 + 2 = 1 + 2 at indices 0, 2, 1, 3
Result with sorting: true

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

4-Sum algorithm failing with duplicate values in Java - Stack Overflow

1 Answer 1

与本文相关的文章

评论列表(0)