題目

https://leetcode.com/problems/combination-sum-iii/

題解

回溯法（back tracking）是一種選優(yōu)搜索法。可以理解為通過(guò)選擇不同的岔路口尋找目的地，一個(gè)岔路口一個(gè)岔路口的去嘗試找到目的地。如果走錯(cuò)了路，繼續(xù)返回來(lái)找到岔路口的另一條路，直到找到目的地。

對(duì)于本題來(lái)說(shuō)，維護(hù)一個(gè) boolean[] arr 數(shù)組，用來(lái)記錄每個(gè)元素是否被選累加。process 的過(guò)程是，從左至右遍歷，對(duì)于每一個(gè)位置來(lái)說(shuō)，都有加與不加兩種選擇。分別對(duì)這兩種選擇調(diào)用 process，以此類推。直到越界，或累加和恰好為目標(biāo)值時(shí)，返回。

import java.util.ArrayList; import java.util.List;class Solution {int target = 0;List<List<Integer>> resultList;public List<List<Integer>> combinationSum3(int k, int n) {target = n;resultList = new ArrayList<>();process(new boolean[10], 1, 0, k);return resultList;}public void process(boolean[] arr, int i, int sum, int valid) {if (i >= 10 || sum > target || valid <= 0) return; // 越界if (sum + i == target && valid - 1 == 0) { // 成功匹配之后 由于后面的數(shù)字只可能更大 所以后面不再可能匹配 直接返回即可arr[i] = true;ArrayList<Integer> list = new ArrayList<>();for (int j = 1; j < 10; j++) {if (arr[j]) list.add(j);}resultList.add(list);}process(arr, i + 1, sum, valid);arr[i] = true; // 修改之后要恢復(fù)原值 以保持原狀返還給上一個(gè)函數(shù)繼續(xù)使用process(arr, i + 1, sum + i, valid - 1);arr[i] = false;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 216. Combination Sum III | 216. 组合总和 III（Java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。