iT邦幫忙

0

排列組合DFS問題

題目:一個陣列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?
拜托大家教一下我,謝謝

1 個回答

0
robertwang
iT邦新手 5 級 ‧ 2021-09-25 12:54:29
最佳解答

理論上不重複的題目,暴力寫法都是雙層迴圈,所以除了遞迴之外還是要一層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();
    }
  }
}
amyqaz iT邦新手 5 級 ‧ 2021-09-27 14:33:31 檢舉

感謝robertwang分享,我先研究看看,演算法對我來說有點難,得花點時間理解,不會再跟您請教,謝謝

amyqaz iT邦新手 5 級 ‧ 2021-10-01 14:09:55 檢舉

謝謝大大,雖然默寫或是變化題可能還是會被考倒,不過基本的跑法我大概了解了,感謝

遞迴要多看幾種題目會更加清楚,加油

我要發表回答

立即登入回答