題目:一個陣列EX:{1,2,3},數字不重複,將所有排列組合列出來
想詢問各位程式問題,我找到答案卻看不懂
class DFS
{
static void dfs(List<List<Integer>> results, List<Integer> path, int[] nums) {
if(path.size() == nums.length) {
results.add(new ArrayList<>(path));
return;
}
else {//不懂這段
for(int i = 0; i < nums.length; i++) {
if(path.contains(nums[i]))
continue;
path.add(nums[i]);
dfs(results, path, nums);
path.remove(path.size() - 1); //#backtracking
}
}
}
public static void main(String[] args) {
int []nums={1,2,3};
List<List<Integer>> results = new ArrayList<>();
dfs(results, new ArrayList(), nums);
/* */
for(int i=0;i< results.size();i++){
for(int j=0;j<results.get(i).size();j++){
System.out.print(results.get(i).get(j));
}
System.out.println("");
}
}
}
我對DFS這段
for(int i = 0; i < nums.length; i++) {
if(path.contains(nums[i]))
continue;
path.add(nums[i]);
dfs(results, path, nums);
path.remove(path.size() - 1);
}
真的是轉不過來,為何還要 path.remove(path.size() - 1);
dfs(results, path, nums);是遞迴吧?可是為何還要用for?
拜托大家教一下我,謝謝
理論上不重複的題目,暴力寫法都是雙層迴圈,所以除了遞迴之外還是要一層for,建議如果想不通就多印一點出來就比較容易看得懂。
他的作法是一個一個數字下去找,遞迴的概念就是拆解,設定一個基準值後返回,這邊的基準值就是nums得長度,
順序是
先找到1 -> 開始遞迴 -> 1、1 重複跳過 -> 1 、2 再往下遞迴 -> 1 & 2 都重複跳過 -> 1、2、3往下遞迴 -> 長度到達基準值返回 -> path.remove(path.size() - 1)
也就是123長度已經最長,不會再更長,所以刪掉最後一個變成12再繼續去遞迴,假設題目是1234那這時候還有124這個答案要找出來->這邊12之後也只有123所以再退回一次path.remove(path.size() - 1)
變回1 -> 再繼續往下找13 ......
好像沒有講得很清楚,我加了一些print跟稍微簡化了for看起來不要這麼複雜,實際跑跑看應該就蠻清楚了。
class DFS
{
static void dfs(List<List<Integer>> results, List<Integer> path, int[] nums) {
if(path.size() == nums.length) {
results.add(new ArrayList<>(path));
}
else {//不懂這段
for (int num : nums) {
if (path.contains(num)) {
System.out.println("return path" + path);
continue;
}
path.add(num);
System.out.println("path" + path);
dfs(results, path, nums);
System.out.println( "before remove path" + path);
path.remove(path.size() - 1); //#backtracking
System.out.println( "after remove path" + path);
}
}
}
public static void main(String[] args) {
int []nums={1,2,3};
List<List<Integer>> results = new ArrayList<>();
dfs(results, new ArrayList(), nums);
/* */
for (List<Integer> result : results) {
for (Integer integer : result) {
System.out.print(integer);
}
System.out.println();
}
}
}