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

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

You start with the simplest cases, making various assumptions

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.