Recursive Backtracking


Maze


Permute

简要
对于给定vector(v1)中的元素进行全排列 eg:{“a”,”b”,”c”}

解决方案
1.寻找自相似 对于给定数目元素的全排列问题,观察结果可见排列结果为各元素与其余元素全排列结果的全连接,类比骰子(每次骰子结果与其余骰子结果的全连接),但是骰子元素有重复,例如{1,1,1}。
2.采用另一vector(v2)来存储当前选择的元素,追踪连接结果

Recursion

  • base case
    v1为空时输出v2的全排列结果
  • choice
    遍历v1的各元素,将当前元素存储到v2中,记录连接结果
  • explore
    求其余元素的全排列结果 (注意是其余元素,因此需要先将当前选择的元素从v1中弹出)
  • unchoice backtracking
    continue时需要恢复v1,v2原始状态
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

void PermuteHelper (Vector<string> ori,Vector<string> chosen) {
if(ori.isEmpty()) {
cout << chosen << endl;
} else {
for(int i=0;i<ori.size();i++) {
//dynamic
cout<<recursionIndent()<<"ori : "<<ori<<"chosen : "<<chosen<<endl;
//choice
chosen.add(ori[i]);
//expore following choice
string store=ori[i];
ori.remove(i);
PermuteHelper(ori,chosen);
//un-chocie
ori.insert(i,store);
chosen.removeBack();
}
}

}

void Permute (Vector<string> ori) {
Vector <string> chosen;
PermuteHelper(ori,chosen);
}