Recursive Backtracking

SubLists

Question

Decision Tree

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//Lecture10 subLists
void subListsHelper (Vector<string>& ori,Vector<string>& chosen) {
    if(ori.isEmpty()) {
        cout << chosen <<endl;
    } else {
        //every possible choice  --include "a" or not
        //choose  -try with "a"  ...  try without "a"
        cout<<recursionIndent()<<"ori : "<<ori<<"chosen : "<<chosen<<endl;

        string store=ori[0];
        ori.remove(0);

        //explore

        //case 1 explore exclude "a"
        subListsHelper(ori,chosen);

        //case 2 explore include"a"
        chosen.add(store);
        subListsHelper(ori,chosen);

        //unchoose
        ori.insert(0,store);
        chosen.removeBack();
    }

}

void subLists (Vector<string>& ori) {
    Vector <string> chosen;
    subListsHelper(ori,chosen);
}