【回溯】C038_LQ_凑算式（暴搜）

一、Problem

29

二、Solution

方法一：dfs

• 全排列枚举所有情况。
• 判断是否合法时记得注意精度问题，可选择通分，或者转为浮点数。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
    static int N = 9;
    static int[] A;
    static int cnt;
    static boolean gg() {
        return A[0]+A[1]*1.0/A[2]+(A[3]*100+A[4]*10+A[5])*1.0/(A[6]*100+A[7]*10+A[8])==10;
    }
    public static void main(String[] args) throws IOException {  
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = i+1;
        }
        dfs(0);
        System.out.println(cnt);
    }
    private static void dfs(int k) {
        if (k == N-1){
            if (gg())
                cnt++;
            return;
        }
        for (int i = k; i < N; i++) {
            swap(A, i, k);
            dfs(k+1);
            swap(A, i, k);
        }
    }
    private static void swap (int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

复杂度分析

• 时间复杂度：$O(2^n)$O(2n)，
• 空间复杂度：$O(n)$O(n)，