Lets take an array of size n. There 2ⁿ possible subarrays of this array. Lets take the example array of size 4: [1, 2, 3, 4]. There are 2⁴ sub arrays.

Sub array of the empty set ([]) is the 0^th one (0000). The subarray of [1], is the second one (0001), the subarray of [2] is the second one… (0010) and the subarray [1, 2] is the third one (0011). You should see where this is going.

No recursion is necessary for this. The set of the sub arrays is the binary representation of the the n^th value ranging from 0 to 2ⁿ – 1.

With this realization, the generation of all of the subarrays for a given arrays should be a trivial matter of iterating of the integers and looking at them as bit fields for if a particular element is in the subarray or not.

See also Number of k combinations for all k on Wikipedia.

I would point out that this is probably the right way to do it in C and similar languages. Trying to force recursion, lists, and backtracking onto what would otherwise be a simple iterative problem with a clear and understandable answer may not the best approach.

Note that other proposed answers to this quickly become functional programming examples and solutions. Functional programming is great. However, in a language not suited for such trying to force this paradigm of programming on it would be akin to writing C code in Lisp – it might not be the best way to approach the problem.

I should further point out that the problem hinted at in the question is:

For instance say I have a array with [1,2,3,4] and my destination value is 5. I am trying to find all possible combinations that equal to my destination value.

This is a well known problem known as the subset sum problem and has a number of approaches to solve it… generating all the subsets of the array is not required (or even desired) for the faster approaches to solve it.

You want to enumerate recursively the set of sublists of 1 :: 2 :: 3 :: 4 :: [] which sums to 5. (The :: is the OCaml notation for the list construction.) The recursive step in list processing is splitting the list in its head 1 and its tail 2 :: 3 :: 4 :: [] — can we describe our set in these terms?

There is two kinds of sublists of 1 :: 2 :: 3 :: 4 :: [] which sums to 5:

• The first kind consists of lists starting with 1 and followed by a list which sums to 4 = 5 - 1.
• The second kind consists of sublists of 2 :: 3 :: 4 :: [] summing to 5.

Wonderful! If we call partition the function int list -> int -> int list list finding all the required sublists, the description above just describes how to define partition lst for lists lstof length n given its definition for lists of length n-1.

Writing the function in OCaml is then staightforward:

let rec partition lst w =
  if w = 0 then
    [[]]
  else
    match lst with
      | [] -> []
      | hd :: tl -> firstkind hd tl (w - hd) @ partition tl w
and firstkind hd tl w =
  List.map (fun lst -> hd :: lst) (partition tl w)

I’m assuming for the purpose of this exercise that you don’t want any repeats. For example, the combinations for [1..4] are

[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],
 [1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]

If not, the process is really the same for all recursive functions: figure out your bases cases, and figure out your larger problem in terms of a smaller problem.

We’re going to create a function subarrays that takes a list and returns a list of lists—one for every combination, so:

subarrays :: [a] -> [[a]]

The base case is usually very easy. In this case, the subarrays for an empty list is an empty list, so:

subarrays [] = []

The recursive step for list functions almost always breaks it into the first element, called the “head” (denoted here by x), and the rest of the list, called the “tail” (denoted here by xs). We assume we already know the correct answer for the tail, and we use that to build an answer for the head. Here we assign the symbol combos to the answer for the tail:

subarrays (x:xs) = let combos = subarrays xs

So far this is relatively boilerplate code that you find on almost every recursive function in one form or another. The tricky part is now that we’ve solved it for a smaller list, how do we add another layer?

For an example, assume combos contains all the solutions for [2,3,4] and you’re building a list that also contains solutions containing 1. In this case, you can do one of three things to build the larger list.

• Just have 1 by itself. ([x])
• Just have all the other combos by themselves. (combos)
• Have all the other combos with a 1 added. (map (x:) combos)

Then return a list containing all those possibilities:

[x] : map (x:) combos ++ combos

That’s really all there is to it. Here’s the complete program in Haskell with the sum test function as well:

subarrays :: [a] -> [[a]]
subarrays [] = []
subarrays (x:xs) = let combos = subarrays xs
                   in [x] : map (x:) combos ++ combos

combosSumTo :: Int -> [Int] -> [[Int]]
combosSumTo x = filter (y -> sum y == x) . subarrays

As far as how I came up with the three things, you just sort of have to practice, and test and repeat. When I first wrote this just now, I accidentally forgot the [x] part, but that showed up in my tests. The trick is don’t try to recurse down the stack in your head. Just assume the recursive call gives you the correct answer for the tail of the list.