use std::iter::repeat;
impl Solution {
    pub fn makesquare(matchsticks: Vec<i32>) -> bool {
        let mut matchsticks = matchsticks;
        let mut sum = 0;
        for num in matchsticks.iter() {
            sum += num;
        }
        if sum & 3 != 0 {
            return false;
        }
        let mut dp: Vec<i32> = repeat(0).take(1 << matchsticks.len()).collect();
        return Solution::process(&mut matchsticks, 0, 0, sum >> 2, 4, &mut dp);
    }

    fn process(
        arr: &mut Vec<i32>,
        status: i32,
        cur: i32,
        len: i32,
        edges: i32,
        dp: &mut Vec<i32>,
    ) -> bool {
        if dp[status as usize] != 0 {
            return dp[status as usize] == 1;
        }
        let mut ans = false;
        if edges == 0 {
            ans = if status == (1 << arr.len()) - 1 {
                true
            } else {
                false
            };
        } else {
            let mut i = 0;
            while i < arr.len() as i32 && !ans {
                if ((1 << i) & status) == 0 && cur + arr[i as usize] <= len {
                    if cur + arr[i as usize] == len {
                        ans |= Solution::process(arr, status | (1 << i), 0, len, edges - 1, dp);
                    } else {
                        ans |= Solution::process(
                            arr,
                            status | (1 << i),
                            cur + arr[i as usize],
                            len,
                            edges,
                            dp,
                        );
                    }
                }
                i += 1;
            }
        }
        dp[status as usize] = if ans { 1 } else { -1 };
        return ans;
    }
}

fn main() {
    let matchsticks = vec![1, 1, 2, 2, 2];
    let ans = Solution::makesquare(matchsticks);
    println!("ans = {:?}", ans);
}

struct Solution {}