welcome
0%

c-回溯法模板与例题

发表于 更新于 分类于

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
try(int i)
 {
    if(i>n)
        输出结果;
    else
         {
       for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
        {
           if(fun(j)) // 满足限界函数和约束条件
             {
                a[i] = j;
                ... // 其他操作
                 try(i+1);
                 回溯前的清理工作（如a[i]置空值等）;
            }
         }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
   List<List<Integer>> result=new ArrayList<List<Integer>>();
   public List<List<Integer>> combine(int n, int k) {
       List<Integer> list=new ArrayList<Integer>();
       backtracking(n,k,1,list);
       return result;
    }
   public void backtracking(int n,int k,int start,List<Integer>list){
       if(k<0) return ;
       else if(k==0){
           result.add(new ArrayList(list));
       }else{
           for(int i=start;i<=n;i++){
                list.add(i);
                backtracking(n,k-1,i+1,list);
                list.remove(list.size()-1);
            }
       }
    }
}