回溯——回溯模板 && 78.子集 && 90.子集II

这题是最经典的回溯题目了，回溯树中的每一条途径的路径都要加入结果集。

常见的回溯模板如下：

    List> result = new ArrayList<>();
    ArrayList path = new ArrayList<>();
    private void backtracking() {
        if (符合结果集的判定) {
            //当前路径的深copy
            result.add((ArrayList) path.clone());
        }

        for (回溯树路径集: 当前路径) {
            if (当前路径已经不可能符合结果集) {
                //剪枝
                break;
            }
            path.add(当前节点 in 回溯树);
            backtracking(当前回溯树的子树);
            path.remove(path.size() - 1);
        }
    }



78.子集——因为无论长短的每条路径都要加入结果集，则 if (true)



    public void backtracking(int[] nums, int startIndex) {
        result.add((ArrayList) path.clone());

        for (int i = startIndex; i < nums.length; ++i) {
            path.add(nums[i]);
            backtracking(nums, i+1);
            path.remove(path.size() - 1);
        }
    }




90.子集II——相较于78，90传入的是一个有重复元素的数组，则需要将原数组排序，然后在path的每次更新中，跳过已经加入path中的元素：



    private void backtracking(int[] nums, int startIndex) {
        result.add((ArrayList) path.clone());

        for (int i = startIndex; i < nums.length; ++i) {
            //跳过本次回溯过程中已经加入到path中的元素
            if (i > startIndex && nums[i-1] == nums[i]) {
                continue;
            }
            path.add(nums[i]);
            backtracking(nums, i+1);
            path.remove(path.size() - 1);
        }
    }

						  
					  
						
							


						

							
							
			LeetCode							
						



						

						
						


						

						
					
					

					
					

						
相关

						

				
						
			

																
								

										
【LeetCode每日一题】员工的重要性

									
									

								 

        

								

							
							

																
								

										
【LeetCode每日一题】整数反转

									
									

								 

        

								

							
							

																
								

										
【LeetCode】—— 翻转二叉树

									
									

								 

        

								

							
							

																
								

										
【python】Leetcode每日一题-森林中的兔子

									
									

								 

        

								

							
							

																
								

										
【python】Leetcode每日一题-132模式

									
									

								 

        

								

							
							

																
								

										
Leetcode练习第一题

									
									

								 

        

								

							
							

																
								

										
LeetCode刷题总结-数组篇（上）

									
									

								 

        

								

							
							

																
								

										
Leetcode字符串算法

									
									

								 

        

								

							
							

																
								

										
【leetcode】36. Valid Sudoku（判断能否是合法的数独puzzle）

									
									

								 

        

								

							
							

																
								

										
【leetcode】167. Two Sum II - Input Array Is Sorted

									
									

								 

        

								

							
							

																
								

										
leetcode316 去除重复字母

									
									

								 

        

								

							
							

																
								

										
[LeetCode] 395. 至少有 K 个重复字符的最长子串

									
									

								 

        

								

							
							
            
            
            
                                    
           
  			
						

					

					
				

				

														
					
					

					
									

					
									   
标签

										

										
    
										

									

										
										

									

					

					
				


			
		
		
		
			


						





	

	
一品网 冀ICP备14022925号-6