CODEWITHSUNDEEP
arraysalgorithmloopsrecursionmethods
eldlit
eldlit

Reputation: 63

How do i find all possible sums of N elements in an array?

I'm looking for advice on how to find all possible sums of N elements. For example, I have an array

int []arr={91,58,89,87,25,65,21};

For some int n=3;

I need to find all possible sums of 3 elements in this array. In the beginning, it looked easy for me as I would find all sums of subarrays of size 3 but I am not sure of subsequences of size 3 . I found similar questions on Google and the solution was to use recursion. I'm not sure I really understand how to solve this one with my conditions, hope you could give me an advise and example so I could solve this one! I'm not sure my initial code is need since it works linearly.

Thank you in advance.

Upvotes: 2

Views: 2542

Answers (3)

Egor
Egor

Reputation: 1409

I have this solution for variable length of subsequences. Java code:

public static void main(String[] args) {
    int[] arr = {91, 58, 89, 87, 25, 65, 21};
    int n = 3;

    sum(arr, 0, n, 0);
}

public static void sum(int[] arr, int startIdx, int deep, int currSum) {
    if (deep == 1) {
        for (int i = startIdx; i < arr.length; i++)
            System.out.println(currSum + arr[i]);
    } else {
        for (int i = startIdx; i < arr.length; i++)
            sum(arr, i + 1, deep - 1, currSum + arr[i]);
    }
}

UPD: If you need to get result as list, you may use this variation:

public static void main(String[] args) {
    int[] arr = {91, 58, 89, 87, 25, 65, 21};
    int n = 3;

    List<Integer> sums = sum(arr, n, 0);
    System.out.println(sums);
}

public static List<Integer> sum(int[] arr, int deep, int currSum) {
    List<Integer> list = new ArrayList<>();
    if (deep == 1) {
        for (int value : arr) list.add(currSum + value);
    } else {
        for (int i = 0; i < arr.length; i++)
            list.addAll(sum(Arrays.copyOfRange(arr, i + 1, arr.length), deep - 1, currSum + arr[i]));
    }
    return list;
}

Upvotes: 2

KnightKnight
KnightKnight

Reputation: 217

Please find this helpful because it seems you are not aware of the terms Subsequences and Subarrays. Subarrays and Subsequences what are they?

Now that if You know what a subsequence is, your question demands you to find count subsequences of size N which have distinct sums. I will attempt a recursive version of C++ code here , if you don't know C++ syntax I will try Java :).

void function(int size,int n,int sum,set<int> Set,int arr[],int iterator)
{
if(iterator>=arr.size())
    return;
if(size==n)
{
    Set.insert(sum);
    return;
}
function(size+1,n,sum+arr[iterator],Set,arr,iterator+1);
function(size, n,sum+arr[iterator],Set,arr,iterator+1);
}

The size of you Set will be your desired Answer.

Upvotes: 1

Yash Shah
Yash Shah

Reputation: 1654

You can easily solve this problem in O(n^3) time complexity using three for-loops iterating over each element.

Take a look at the python code below:

array = [91,58,89,87,25,65,21]
length = len(array)
n = 3

arraySum = []

for i in range(length - n + 1):
    sn = array[i]
    for j in range(i+1,length - n + 2):
        sn = sn + array[j]
        for k in range(j+1,length):
            sn = sn + array[k]
            arraySum.append(sn)

print(arraySum)

Upvotes: 2

Related Questions