leetcode 526. Beautiful Arrangement | 526. 优美的排列（回溯）

r囧r小猫 2022-09-12 10:50 191阅读 0赞

## 题目 ##

[https://leetcode.com/problems/beautiful-arrangement/][https_leetcode.com_problems_beautiful-arrangement]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

首先分析，全排列一个一个试的话（如下图），时间复杂度O(n^2)，当n=15时，总共87178291200种情况，是肯定会超时的。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

然后想想怎么剪枝。因为当一个位置的一个数字不可用时，后面也就没必要在尝试了。所以这种情况下，剪枝，不用继续往后走。递归如下。  
递归函数中，i 是当前填写到的位置，seen 是已经用过的数字。

class Solution { 
        public int countArrangement(int n) { 
            return process(n, 1, new HashSet<>());
        }
    
        public int process(int n, int i, Set<Integer> seen) { 
            int count = 0;
            if (i > n) return 1;
            for (int j = 1; j <= n; j++) { 
                if (!seen.contains(j) && (i % j == 0 || j % i == 0)) { 
                    seen.add(j);
                    count += process(n, i + 1, seen);
                    seen.remove(j);
                }
            }
            return count;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_beautiful-arrangement]: https://leetcode.com/problems/beautiful-arrangement/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7d3d299188ce49c798ac3cb3eda714dc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ce0d0a972030460993dc18945eaf4a3b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/18e1b94778d94105b900abcec11e0c24.png