hot100之回溯上
<h3 id="全排列046">全排列(046)</h3><pre><code class="language-java">class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int n = nums.length;
List<Integer> path = new ArrayList<>(n);
for (int num : nums){
path.add(num);
}
backTrack(0, path, n);
return res;
}
private void backTrack(int idx, List<Integer> path, int len){
if (idx == len-1){
res.add(new ArrayList(path));
return;
}
for (int i = idx; i < len; i++){
Collections.swap(path, idx, i);
backTrack(idx+1, path, len);
Collections.swap(path, idx, i);
}
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>根据排列组合, 我们可以得到 答案的数量为 <code>nums.length()</code>的阶乘</p>
<p>假设 n = <code>nums.length</code> =3</p>
<p>对于第一个数的选择有三种可能 ∗3</p>
<p>对于第二个数的选择有两种可能 ∗2(两个数未选)</p>
<p>对于第三个数的选择有一种可能 ∗1(一个数未选)</p>
<p>有以下关键代码</p>
<pre><code class="language-java">for (int i = idx; i < len; i++){
Collections.swap(path, idx, i);
backTrack(idx+1, path, len);
Collections.swap(path, idx, i);
}
</code></pre>
<h3 id="子集078">子集(078)</h3>
<pre><code class="language-java">class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
List<Integer> path = new ArrayList<>();
backTrace(0, path, nums, n);
return res;
}
private void backTrace(int idx, List<Integer> path, int[] nums, int len){
if (idx == len){
res.add(new ArrayList(path));
return;
}
path.add(nums);
backTrace(idx+1, path, nums, len);
path.remove(path.size()-1);
backTrace(idx+1, path, nums, len);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>标准的背包问题, 选或不选</p>
<h3 id="电话号码的字母组合017">电话号码的字母组合(017)</h3>
<pre><code class="language-java">class Solution {
String[] mapping = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
int n = digits.length();
if (!digits.isEmpty()) backTrace(0, digits, new StringBuilder(), n);
return res;
}
private void backTrace(int idx, String digits, StringBuilder builder, int len){
if (idx == len){
res.add(builder.toString());
return;
}
char c = digits.charAt(idx);
c -= '0';
for (char d : mapping.toCharArray()){
builder.append(d);
backTrace(idx+1, digits, builder, len);
builder.deleteCharAt(builder.length()-1);
}
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>标准简单回溯</p>
<h3 id="组合总和039">组合总和(039)</h3>
<pre><code class="language-java">class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<Integer> path = new ArrayList<>();
backTrace(0, target, path, candidates);
return res;
}
private void backTrace(int idx, int target, List<Integer> path, int[] candidates){
if (target == 0){
res.add(new ArrayList(path));
return;
}
if (idx == candidates.length || target < candidates)return;
backTrace(idx+1, target, path, candidates);
path.add(candidates);
backTrace(idx, target - candidates, path, candidates);
path.remove(path.size()-1);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>我愿称他为原地背包, 也不知道有没有这种说法</p>
<h3 id="括号生成022">括号生成(022)</h3>
<pre><code class="language-java">class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
StringBuilder builder = new StringBuilder();
backTrace(n, n, builder);
return res;
}
private void backTrace(int lef, int rig, StringBuilder builder){
if (lef > rig || lef < 0 || rig < 0)return;
if (lef == 0 && rig == 0){
res.add(builder.toString());
return;
}
backTrace(lef-1, rig, builder.append('('));
builder.deleteCharAt(builder.length()-1);
backTrace(lef, rig-1, builder.append(')'));
builder.deleteCharAt(builder.length()-1);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>标准回溯 + 括号 →<右括号数量不能大于左括号>的限制条件</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18931033
頁:
[1]