# Given elements in an array find combinations equal to the target value

I've been pondering this problem for quite some time now and for some reason it doesn't go through my head. If I am given an array [1,2,3,4] and the destination is 5. I want to get all possible combinations from the array to add to the target.

So, one approach I can think of is

``````1!=5
1+2!=5
1+3!=5
1+4=5
//now check with combos of 3 digits.
1+2+3 !=5
1+2+4 !=5
//now check with combos of 4...however at this point i realized i missed the combination 1+3+4 also.
```

```

I've seen several answers on the internet, but they don't seem to make sense and I'm not very interested in other answers or codes, I want to learn how to think correctly, so I can solve problems like this. I was wondering if someone can help me and help me figure out this problem and also how should I think to solve such problems. At this point, I really don't care about efficiency because I haven't even been able to articulate the approach, so all approaches are welcome. Also I prefer to use only array and regular loops rather than any other data structures like hash as I haven't studied them yet.

+3

source to share

Since you said you wanted "ways of thinking," this is one way.

1) Suppose all your array elements are less than the target value. - a simple checkout procedure will help with execution.

High-level steps

You need to figure out a way to get all possible permutations of a number.

Then add each permutation element and check if the sum matches "destination" (this is an easier task).

now comes to the main problem:

how to get all possible permutations?

Solution Approach Suppose we have an array of one element: Cooling is obvious :)

Next, we have an array of two elements: You define the size of the array: 2 You have to iterate over this size, because your combinations will be less than or equal to this size. Your first iteration will be 1. ie. you're looking for a combination of size one It's simple: you iterate over the array one at a time.

The next iteration will look for combinations of size 2. Since the value of iteration (2) is equal to the size of the array (2), you know that there is only one possible case.

Now let's process an array of size 3:

for permutations of size 1, you know what to do.

for permutations of size 3, you know what a combination is.

for permutations of size 2, you need a different iteration. you iterate over the array, hold the current element of the array, and rearrange the remainder of the size 2 array.

Then you iterate over the second and then the third element and rearrange the remainder of the size array (3-1 = 2)

-------------------------------- UPDATED ----------- ------ ---------------------------------

Next, let's try an array containing 4 elements Lets call A (4)

For permutations of size 1 and permutations of size 4, this is obvious.

For permutations of size 3, you will repeat the process of what you did to get permutations of size 2 for an array of size 3. You will be holding one element, you will be left with an array of size 3. Let's call it A (3)

But remember, you also need permutations of size 2. You can define all permutations of size 2 from this array of size 3 itself by applying the same reusable component. This becomes a recursive call.

So, essentially, you should be doing something most of the time.

'If you have an array of size n; A (n), you need to iterate through it while holding the element to be iterated over and you will have an array of size n-1; A (n-1) '

then repeat the recursive call. and replace n with n-1 in the bold line

So, in essence, you can see that this turns into a recursive problem.

This is one way of thinking about solving this problem. I hope I have explained the thinking process clearly.

------------------------------------------ EXAMPLE- ------ -----------------------------------

Suppose we have an array {1,2,3,4,5}

and our function looks like

`````` function G (int[] array ) {
Looping over array{
remove array[index] from array
you are left with restOfTheArray .// store it some where.
then
make a recursive call to G with restOfTheArray;
}
}
```

```

Dry running for cycle:

`````` Dry run 1:
funtion G (Array (n ) ) {
Looping over {1,2,3,4,5}{
first value while looping is 1, remove it from the array;
you have {2,3,4,5}.// store it some where.
then
make a recursive call to G with {2,3,4,5}
}
}

Dry run 2:
funtion G (Array (n ) ) {
Looping over {1,2,3,4,5}{
second value while looping is 2, remove it from the array;
you have {1,3,4,5}.// store it some where.
then
make a recursive call to G with {1,3,4,5}
}
}
```

```

etc.

now let's look at the dry running of the recursive call:

``````  Dry Run 1.1
funtion G (Array (n ) ) {
Looping over {1,2,3,4,5}{
First value while looping is 1, remove it from the array;
you have {2,3,4,5}.// store it some where.
then
make a recursive call to G with {2,3,4,5}
}
}

Dry Run 1.2

funtion G (Array (n ) ) {
Looping over {2,3,4,5}{
First value while looping is 2, remove it from the array;
you have {3,4,5}.// store it some where.
then
make a recursive call to G with {3,4,5}
}
}
```

```

etc.

+1

source

All Articles