深度优先搜索(DFS)

解题步骤

DFS 通用解题步骤

  1. 截止条件
  2. 遍历候选节点
  3. 筛选

DFS搜索执行顺序

  • 如下图

dfs

力扣对应题目

面试题 08.07. 无重复字符串的排列组合

通用DFS解题代码

public static String dfs(char[] chars,Stack stack) {
        // 1.截止条件
        if (stack.size()==chars.length) {
            List<String> list = new ArrayList<>();
            System.out.println(stack.toString());
            return stack.toString();
        }

        // 2.遍历候选节点
        for (int i=0;i<chars.length;i++) {
            char c = chars[i];
            // 2.1 筛选
            if (chars[i]!='0') {
                stack.push(c);
                chars[i] = '0';
                dfs(chars,stack);
                stack.pop();
                chars[i] = c;
            }
        }
        return stack.toString();
    }

参考视频