Leetcode---括号生成--回溯

括号生成

題目連結：括号生成

思路：

• 回溯法的結果集一般是搜尋過程中動态生成的
• 利用條件限制不合法的子集生成，避免龐大的無效遞歸
• 當結果不滿足條件時傳回到上一層，應當恢複為之前的狀态
• 這裡兩個存儲空間，是以互不影響

public List<String> generateParenthesis(int n) {
		//構造一個結果集
		List<String> list = new ArrayList<String>();
		if(n==0) {
			return list;
		}
		//調用回溯
		traceback(list,"",0,0,n);
		return list;
    }
	
	public void traceback(List<String> list,String temp,int left,int right,int n) {
		//如果左括号越界,或者右括号越界,或者右括号比左括号多,都直接return,不滿足正常括号的要求
		//也可視為剪枝,不滿足要求的不再深入遞歸
		if(left>n||right>left||right>n) {
			return ;
		}
		//達到遞歸深度了，并且滿足要求的括号添加至結果集
		if(left==n&&right==n) {
			list.add(temp);
			return ;
		}
		//注意此時temp+'('已經相當于重新申請了一塊記憶體，而不是和temp占用同一塊，即temp記憶體中的值沒有變化
		//下一層添加'('或者')'均可,是以有兩種遞歸
		traceback(list,temp+'(',left+1,right,n);
		//回溯需要傳回上一層,是以要儲存之前的值不能被破壞,這裡由于是兩塊記憶體,是以并沒有影響
		traceback(list,temp+')',left,right+1,n);
	}