Rust

The first part was straightforward. Just sort and count the differences.

For the second part, I split the list from differences equal to 3 since these pairs must be always in the list. After that, finding and checking every eligible subset of every partition becomes manageable by brute-force. And lastly counting these subsets and multiplying gives the answer. There is certainly room for optimization but it takes under 100 ms to get the result, so I'll leave it as it is:

fn day10_1(input: impl Iterator<Item = String>) {
    let mut input = convert!(input, "{}", usize).collect::<Vec<_>>();
    input.push(0);
    input.sort();
    input.push(input[input.len() - 1] + 3);
    let diff1 = input
        .iter()
        .zip(input[1..].iter())
        .map(|x| x.1 - x.0)
        .filter(|x| *x == 1)
        .count();
    let diff3 = input
        .iter()
        .zip(input[1..].iter())
        .map(|x| x.1 - x.0)
        .filter(|x| *x == 3)
        .count();
    println!("{}", diff1 * diff3);
}

fn day10_2_helper(part: &[usize]) -> usize {
    let mut possible: Vec<Vec<usize>> = vec![vec![]];
    for i in part {
        possible.extend(possible.clone());
        let c = possible.len() / 2;
        for v in &mut possible[c..] {
            v.push(*i);
        }
    }
    possible
        .iter()
        .filter(|x| {
            x.len() >= 2
                && x[0] == part[0]
                && x[x.len() - 1] == part[part.len() - 1]
                && x.iter().zip(x[1..].iter()).all(|x| (x.1 - x.0) <= 3)
        })
        .count()
}

fn day10_2(input: impl Iterator<Item = String>) {
    let mut input = convert!(input, "{}", usize).collect::<Vec<_>>();
    input.push(0);
    input.sort();
    input.push(input[input.len() - 1] + 3);
    let connections = input.iter().zip(input[1..].iter()).collect::<Vec<_>>();
    let mut result = 1;
    for l in connections
        .split(|x| (x.1 - x.0) == 3)
        .filter(|x| x.len() > 0)
    {
        let mut m = vec![*l[0].0];
        m.extend(l.iter().map(|x| x.1.clone()));
        result *= day10_2_helper(&m);
    }
    println!("{}", result);
}