0

I am facing some difficulties in backtracking.

  1. How do I define a global list to be used in the problems of backtracking? I saw a couple of answers and they have all suggested using 'global' keyword in front of the variable name, inside the function to use as global. However, it gives me an error here.

  2. Is there any good general method that can be used to get the result, instead of a global variable?

The code below is trying to solve the backtrack problem wherein, a list of numbers is given, and we have to find unique pairs (no permutations allowed) of numbers that add to the target. 

For example, given candidate set [2, 3, 6, 7] and target 7, 

A solution set is: 
[
  [7],
  [2, 2, 3]
] 


       ///////////////////////////////CODE/////////////////////////////


       seen = []
        res = []

        def func(candidates, k, anc_choice):     #k == target

            #global res -- gives me an error --  global name 'res' is not defined

            if sum(anc_choice) == k:
                temp = set(anc_choice)
                flag = 0

                for s in seen:
                    if s == temp:
                        flag = 1
                if flag == 0:
                    seen.append(temp)
                    print(anc_choice)  #this gives me the correct answer
                    res.append(anc_choice)  #this doesn't give me the correct answer?
                    print(res)

            else:
                for c in candidates:
                    if c <= k:
                        anc_choice.append(c) #choose and append
                        if sum(anc_choice) <= k:
                            func(candidates, k, anc_choice) #explore
                        anc_choice.pop() #unchoose

        func(candidates, k, [])

Can someone please provide me answers/suggestions?

Stephen Rauch
  • 47,830
  • 31
  • 106
  • 135
crazyy_photonn
  • 161
  • 3
  • 17

2 Answers2

1

To utilise the global keyword, you first need to declare it global before instantiating it..

global res
res = []

Though from looking at your code. Because the res = [] is outside the function, it is already available globally.

johnashu
  • 2,167
  • 4
  • 19
  • 44
  • 1
    `foo = [] def bar(): global foo ... foo = [1] ` Is it something like this? Sorry, I am new to this. – crazyy_photonn Mar 16 '18 at 03:10
  • 1
    I agree with @johnashu. since you already have res outside the function then that makes it global. You don't need to put the global keyword inside the fuction, you just use it as any other variable. – Carlos M. Mar 16 '18 at 03:48
  • But I am not able to use and change the res inside the recursion. How do I do that? – crazyy_photonn Mar 16 '18 at 04:52
1

There are plenty of reasons why you should not use global variables.

If you want a function that updates a list in the above scope, simply pass the list as argument. Lists are mutable, so it will have been updated after the function call.

Here is a simplified example.

res = []

def func(candidate, res):
    res.append(candidate)

func(1, res)

res # [1]
Olivier Melançon
  • 21,584
  • 4
  • 41
  • 73