给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。

示例 1：
输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。

示例 2：
输入：n = 3
输出：["1/2","1/3","2/3"]

示例 3：
输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。

示例 4：
输入：n = 1
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplified-fractions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

本题跟斐波那契数列和上楼梯算法一样，可以用递归解。即F(n) = 以n为分母的最简分数 + F(n - 1)。

class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        if (n == 1) return res;

        // 分母为n的最简分数
        for (int i = 1; i < n; i++) {
            if (gcd(i, n) == 1) res.add(i + "/" + n);
        }
        // 递归
        res.addAll(0, simplifiedFractions(n - 1));

        return res;
    }

    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

结果如下：