5

I am lost I just can't seem to get my head around backtracking/recursion approaches. I understand how simple recursion problems like factorials work I can even trace those by hand. But when it comes to backtracking problems I am so lost. I keep trying. its been 5 hours I have been reading various approaches on forums and stack exchange but nothing has clicked.

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.

I broke this problem down further to make it even more simple for my self to understand. First I can find all possible combinations of the array and then pass them to another function which checks if the sum of that array equals destination value and then only does it print it.

Can someone advice how to approach this? I am not looking for code/answer I want to be able to think and imagine this in my head clearly.

2
  • i read the answers but nothing seems to get through my head i was wondering if someone can show a simple trace and i am not really familiar with languages like haskell, and olam so that making it harder to understand. can someone show step by step in simple english...or c the pesudocode rather than other languages.. Sep 12, 2014 at 22:16
  • you may refer this: geeksforgeeks.org/find-subarray-with-given-sum I hope it helps Jun 13, 2016 at 12:24

3 Answers 3

7

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

Sub array of the empty set ([]) is the 0th 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 nth value ranging from 0 to 2n - 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.

0
2

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)
1
  • possible to show c pesudocode? not at all familiar with Ocaml Sep 12, 2014 at 21:48
1

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.

2
  • possible to show c pesudocode? not at all familiar with haskell Sep 12, 2014 at 21:47
  • Isn't sub-array means contiguous elements in an array? What you are showing is sub-sets. Correct me if I'm wrong. Feb 25, 2018 at 9:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.