Re: [閒聊] 每日leetcode

[yam276 (史萊哲林的優等生)]

※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/the-number-of-beautiful-subsets/description
: 2597. The Number of Beautiful Subsets
: 給你一個陣列表示一個集合和一個數字k，求出美麗子集數量，美麗子集是一個非空子集合
: ，所有子集元素彼此相差絕對值不會等於k。
:
: 思路：
: 1.回溯法，每次把元素加到當前子集前先檢查是否包含+k或-k，沒有才加。

中間的部分是用別人的方法

我本來的code一直卡在其中一個Test Case

這輩子就這樣了


Code:

impl Solution {
    pub fn beautiful_subsets(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort_unstable();
        let n = nums.len();

        fn solve(nums: &Vec<i32>, k: i32, i: usize, subset: u32) -> i32 {
            if i == nums.len() {
                return 1;
            }

            let mut ans = 0;
            let mut skip = false;

            for j in 0..i {
                if (subset & (1 << j)) != 0 {
                    if (nums[i] - nums[j]).abs() as i32 == k {
                        skip = true;
                        break;
                    }
                }
            }

            if !skip {
                ans += solve(nums, k, i + 1, subset | (1 << i));
            }

            ans += solve(nums, k, i + 1, subset);
            ans
        }

        solve(&nums, k, 0, 0) - 1
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716449881.A.4AA.html
→ SecondRun: 教我
→ yam276: 就是你中間要有j到i的部分判斷是不是等於k
→ yam276: 然後她的(1<<i)的方法太省了 我只能抄了
→ yam276: 用DP時間O比較快 Backtrack寫起來比較省事