排列組合DFS問題

dfs java

amyqaz 2021-09-23 09:30:19 ‧ 1079 瀏覽

分享至

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

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

1 個回答

robertwang

iT邦新手 4 級 ‧ 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();
    }
  }
}